#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 100;
int n, t, m;
vector<int> G[maxn];
int d[maxn], f[maxn], vis[maxn];
vector<int> p[maxn];
int ck;
void dfs(int x, int fa, int dep) {
  d[x] = dep;
  f[x] = fa;
  vis[x] = 1;
  ck = max(ck, dep);
  for (int i = (0); i <= (G[x].size() - 1); ++i) {
    if (G[x][i] == fa || vis[G[x][i]]) continue;
    dfs(G[x][i], x, dep + 1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> t;
  while (t--) {
    ck = 0;
    cin >> n >> m;
    for (int i = (1); i <= (n); ++i) G[i].clear(), p[i].clear(), vis[i] = 0;
    for (int i = (1); i <= (m); ++i) {
      int u, v;
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
    }
    dfs(1, 0, 1);
    if (ck >= (n + 1) / 2) {
      stack<int> ss;
      int vv = 0, val = (n + 1) / 2;
      for (int i = (1); i <= (n); ++i) {
        if (d[i] == val) {
          vv = i;
          break;
        }
      }
      while (vv) {
        ss.push(vv);
        vv = f[vv];
      }
      cout << "PATH\n" << val << endl;
      while (!ss.empty()) {
        cout << ss.top() << " ";
        ss.pop();
      }
      cout << endl;
    } else {
      int val = ((n + 1) / 2 + 1) / 2;
      cout << "PAIRING\n" << val << endl;
      int cnt = 0;
      for (int i = (1); i <= (n); ++i) {
        p[d[i]].push_back(i);
      }
      for (int i = (1); i <= (n); ++i) {
        for (int j = 1; j < p[i].size(); j += 2) {
          cout << p[i][j] << " " << p[i][j - 1] << endl;
          ++cnt;
          if (cnt == val) break;
        }
        if (cnt == val) break;
      }
    }
  }
  return 0;
}
