【題解】Codeforces 1391E. Pairs of Pairs

#include <iostream>
#include <vector>
using namespace std;
 
int t, n, m, a, b, k, d[500005], mx, p[500005];
vector <int> v[500005];
vector <int> dep[500005];
vector <int> ans;
 
void dfs(int x){
    dep[d[x]].push_back(x);
    for (auto i:v[x]){
        if (d[i]) continue;
        d[i] = d[x]+1;
        if (d[i] == k && ans.empty()) ans.push_back(i);
        dfs(i);
        p[i] = x;
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> m;
        k = (n+1)/2;
        ans.clear();
        for (int i = 1; i <= n; i++){
            v[i].clear();
            d[i] = 0;
            p[i] = 0;
            dep[i].clear();
        }
        for (int i = 0; i < m; i++){
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        d[1] = 1;
        dfs(1);
        if (!ans.empty()){
            cout << "PATH\n";
            while (ans.back() != 1) ans.push_back(p[ans.back()]);
            cout << ans.size() << "\n";
            for (auto i:ans){
                cout << i << " ";
            }
            cout << "\n";
            continue;
        }
        cout << "PAIRING\n";
        vector <pair<int, int> > p;
        for (int i = 1; i <= k; i++){
            for (int j = 0; j+1 < dep[i].size(); j+=2){
                p.push_back({dep[i][j], dep[i][j+1]});
            }
        }
        cout << p.size() << "\n";
        for (auto i:p){
            cout << i.first << " " << i.second << "\n";
        }
    }
}