#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
int n, m, T, pos, tot;
int dep[maxn], vis[maxn], fa[maxn], x[maxn], y[maxn];
vector<int> v[maxn], t[maxn];
void dfs(int x, int last) {
  vis[x] = 1, dep[x] = dep[last] + 1, t[dep[x]].push_back(x), fa[x] = last;
  if (dep[x] > dep[pos]) pos = x;
  for (int i = 0; i < v[x].size(); i++) {
    int y = v[x][i];
    if (vis[y]) continue;
    dfs(y, x);
  }
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      v[x].push_back(y), v[y].push_back(x);
    }
    dfs(1, 0);
    if (dep[pos] > (n + 1) / 2) {
      puts("PATH");
      printf("%d\n", (n + 1) / 2);
      for (int i = 1, j = pos; i <= (n + 1) / 2; i++, pos = fa[pos])
        printf("%d%c", pos, i == (n + 1) / 2 ? '\n' : ' ');
    } else {
      puts("PAIRING");
      for (int i = 1; i <= n; i++)
        for (int j = 0; j + 1 < t[i].size(); j += 2)
          tot++, x[tot] = t[i][j], y[tot] = t[i][j + 1];
      printf("%d\n", tot);
      for (int i = 1; i <= tot; i++) printf("%d %d\n", x[i], y[i]);
    }
    for (int i = 1; i <= n; i++) v[i].clear(), t[i].clear(), vis[i] = 0;
    pos = tot = 0;
  }
  return 0;
}
