# 【題解】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";
}
}
}
```