利用 $dfs$ 树的性质。

如果有一个点的深度大于等于 $\lceil \frac{n}{2} \rceil$，那么直接满足第一个条件。

否则利用 $dfs$ 树的性质，一个点的子树之间没有边，因此每个点对都选深度相同的两个点，这样最多浪费 $\lceil \frac{n}{2}\rceil$ 个点，满足条件。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int dep[N],f[N],n,m,_;
vector<int> e[N],vec[N];
vector<pair<int,int> > ans;
void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    f[x]=fa;
    for(int y:e[x]){
        if(dep[y])continue;
        dfs(y,x);
    }
}
void work1(int x){//第一个条件
    puts("PATH");
    printf("%d\n",dep[x]);
    for(;x;x=f[x])printf("%d ",x);
    puts("");
}
void work2(){//第二个条件
    puts("PAIRING");
    for(int i=1;i<=n;i++)vec[i].clear();
    for(int i=1;i<=n;i++)vec[dep[i]].push_back(i);
    ans.clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<vec[i].size();j+=2){
            ans.emplace_back(vec[i][j],vec[i][j-1]);
        }
    }
    printf("%d\n",ans.size());
    for(auto i:ans)printf("%d %d\n",i.first,i.second);
}
int main() {
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)e[i].clear(),dep[i]=0,f[i]=0;
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            e[x].push_back(y);
            e[y].push_back(x);
        }
        dfs(1,0);
        int ff=0;
        for(int i=1;i<=n;i++){
            if(dep[i]>=(n+1)/2){
                work1(i);
                ff=1;
                break;
            }
        }
        if(!ff)work2();
    }
    return 0;
}