Language: C++

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pi acos(-1.0)
#define eps 1e-9
#define ll long long
#define ull unsigned long long
#define sf scanf
#define pf printf
#define nl printf("\n")
#define ps(s) printf("%s",s.c_str())
#define	inf (ll)1e15
#define mod 1000000007
#define mem(x,val) memset(x,val,sizeof x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend() 
#define sz(x) (int)(x).size()
#define test_case int ___t;scanf("%d", &___t);for(int cs=1;cs<=___t;cs++)

using namespace __gnu_pbds;
using namespace std;

inline string getString(int n){char ch[n+5];sf(" %s",ch);return string(ch);}
inline string getLine(int n)
{char ch[n+5];fgets(ch,n+5,stdin);string s=string(ch);s.pop_back();return s;}

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;


const int S=500100;
int n,m;
int par[S+5],dep[S+5];
bool visit[S+5];
vector<int>g[S+5];


void dfs(int u)
{
	visit[u]=true;
	for(int v:g[u])
	{
		if(!visit[v])
		{
			par[v]=u;
			dep[v]=dep[u]+1;
			dfs(v);
		}
	}
}

int main()
{
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //#endif
	test_case
	{
		sf("%d %d",&n,&m);

		for(int i=0;i<=n;i++)g[i].clear();
		for(int i=0;i<m;i++)
		{
			int u,v;
			sf("%d %d",&u,&v);
			g[u].push_back(v);
			g[v].push_back(u);
		}

		par[1]=-1;
		dep[1]=1;
		mem(visit,false);
		dfs(1);

		bool f=true;
		int nodeNeed=n/2+1;
		for(int i=1;i<=n;i++)
		{
			if(dep[i]>=nodeNeed)
			{	
				puts("PATH");
				vector<int>path;
				path.push_back(i);
				while(par[i]!=-1)
				{
					path.push_back(par[i]);
					i=par[i];
				}
				pf("%d\n",sz(path));
				for(int e:path)pf("%d ",e);
				nl;
				f=false;
				break;
			}
		}
		if(f)
		{
			puts("PAIRING");
			vector<int>sameDepth[n+5];
			for(int i=1;i<=n;i++)
			{
				sameDepth[dep[i]].push_back(i);
			}

			vector<pair<int,int>>ans;
			for(int i=1;i<=n;i++)
			{
				for(int j=0;j+1<sz(sameDepth[i]);j+=2)
				{
					int u=sameDepth[i][j];
					int v=sameDepth[i][j+1];
					ans.push_back(make_pair(u,v));
					if(sz(ans)*2>=nodeNeed)
					{
						f=false;
						break;
					}
				}
				if(!f)break;
			}
			pf("%d\n",sz(ans));
			for(pair<int,int> e:ans)pf("%d %d\n",e.first,e.second);
		}
	}
    return 0;
}



































Compiler output:
a.cc: In function 'void dfs(int)':
a.cc:40:9: error: reference to 'visit' is ambiguous
   40 |         visit[u]=true;
      |         ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:80,
                 from a.cc:1:
/usr/include/c++/14/variant:1855:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr std::__detail::__variant::__visit_result_t<_Visitor, _Variants ...> std::visit(_Visitor&&, _Variants&& ...)'
 1855 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
a.cc:34:6: note:                 'bool visit [500105]'
   34 | bool visit[S+5];
      |      ^~~~~
a.cc:43:21: error: reference to 'visit' is ambiguous
   43 |                 if(!visit[v])
      |                     ^~~~~
/usr/include/c++/14/variant:1855:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr std::__detail::__variant::__visit_result_t<_Visitor, _Variants ...> std::visit(_Visitor&&, _Variants&& ...)'
 1855 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
a.cc:34:6: note:                 'bool visit [500105]'
   34 | bool visit[S+5];
      |      ^~~~~
a.cc: In function 'int main()':
a.cc:73:21: error: reference to 'visit' is ambiguous
   73 |                 mem(visit,false);
      |                     ^~~~~
a.cc:15:27: note: in definition of macro 'mem'
   15 | #define mem(x,val) memset(x,val,sizeof x)
      |                           ^
/usr/include/c++/14/variant:1855:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr std::__detail::__variant::__visit_result_t<_Visitor, _Variants ...> std::visit(_Visitor&&, _Variants&& ...)'
 1855 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
a.cc:34:6: note:                 'bool visit [500105]'
   34 | bool visit[S+5];
      |      ^~~~~
a.cc:73:21: error: reference to 'visit' is ambiguous
   73 |                 mem(visit,false);
      |                     ^~~~~
a.cc:15:40: note: in definition of macro 'mem'
   15 | #define mem(x,val) memset(x,val,sizeof x)
      |                                        ^
/usr/include/c++/14/variant:1855:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr std::__detail::__variant::__visit_result_t<_Visitor, _Variants ...> std::visit(_Visitor&&, _Variants&& ...)'
 1855 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
a.cc:34:6: note:                 'bool visit [500105]'
   34 | bool visit[S+5];
      |      ^~~~~