#include <bits/stdc++.h>
using namespace std;
int n,t,m;
const int maxnode=5e5+5;
const int maxline=1e6+5;
int head[maxnode],cnt;
struct edge{int to,pre;}line[maxline*2];
void addline(int u,int v)
{
	cnt++;
	line[cnt].to=v;
	line[cnt].pre=head[u];
	head[u]=cnt;
}
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
			f=-f,ch=getchar();
	}
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int dep[maxnode],ancestor[maxnode];
vector<int>temp[maxnode];
void dfs(int u,int fa)
{
	temp[dep[u]].push_back(u);
	ancestor[u]=fa;
	for(int i=head[u];i;i=line[i].pre)
	{
		int v=line[i].to;
		if(dep[v] || v==fa)
			continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
stack<int>q;
int main()
{
	ios::sync_with_stdio(false);
	t=read();
	while(t--)
	{
		n=read(),m=read();
		for(int i=1;i<=m;i++)
		{
			int u,v;
			u=read(),v=read();
			addline(u,v);
			addline(v,u);
		}
		dep[1]=1;
		dfs(1,0);
		int maxdep=0,maxdep_pos=0;
		for(int i=1;i<=n;i++)
		{
			if(dep[i]>maxdep)
				maxdep=dep[i],maxdep_pos=i;
		}
//		cout<<ceil(n/2.0)<<endl;
		if(maxdep>=ceil(n/2.0))
		{
			int cnt1=0;
			while(maxdep_pos)
			{
				q.push(maxdep_pos);
				cnt1++;
				maxdep_pos=ancestor[maxdep_pos];
			}
			cout<<"PATH"<<endl;
			cout<<cnt1<<endl;
			while(!q.empty())
			{
				cout<<q.top()<<" ";
				q.pop();
			}
			cout<<endl;
		}
		else
		{
			long long cntans=0;
			for(int i=1;i<=maxdep;i++)
				cntans+=temp[i].size()/2;
			cout<<"PAIRING"<<endl;
			cout<<cntans<<endl;
			for(int i=1;i<=maxdep;i++)
			{
				for(int j=0;j<temp[i].size()-1;j+=2)
				{
					cout<<temp[i][j]<<" "<<temp[i][j+1]<<endl;
				}
			}
			for(int i=1;i<=maxdep;i++)
				temp[i].clear();
			for(int i=1;i<=n;i++)
				head[i]=0,dep[i]=0,ancestor[i]=0;
			cnt=0;
		}
	}
	return 0;
}