#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int T, n, m, dep[maxn];
int path[maxn], len, flag;
vector<int> g[maxn];
vector<int> d[maxn];
void dfs(int u, int f) {
  if (flag) return;
  dep[u] = dep[f] + 1;
  d[dep[u]].push_back(u);
  path[dep[u]] = u;
  len = dep[u];
  if (len >= (n + 1) / 2) return flag = 1, void();
  for (auto v : g[u]) {
    if (v == f) continue;
    if (!dep[v]) dfs(v, u);
  }
}
signed main() {
  scanf("%d", &T);
  while (T--) {
    flag = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
      g[i].clear();
      dep[i] = 0;
      d[i].clear();
      path[i] = 0;
    }
    while (m--) {
      int u, v;
      scanf("%d%d", &u, &v);
      g[u].push_back(v);
      g[v].push_back(u);
    }
    dfs(1, 0);
    if (flag) {
      puts("PATH");
      printf("%d\n", len);
      for (int i = 1; i <= len; i++) printf("%d ", path[i]);
      puts("");
    } else {
      puts("PAIRING");
      vector<pair<int, int> > ans;
      for (int i = 1; i <= n; i++) {
        int num = d[i].size();
        for (int j = 0; j < num - 1; j += 2)
          ans.push_back({d[i][j], d[i][j + 1]});
      }
      printf("%d\n", ans.size());
      for (auto i : ans) printf("%d %d\n", i.first, i.second);
    }
  }
}
