#include <bits/stdc++.h>
using namespace std;
int T, n, m, head[500010], o = 0, fa[500010], dep[500010], lst[500010];
bool vis[500010];
struct edge {
  int to, link;
} e[2000010];
void add_edge(int u, int v) {
  e[++o].to = v, e[o].link = head[u], head[u] = o;
  e[++o].to = u, e[o].link = head[v], head[v] = o;
}
void dfs(int u, int pre) {
  dep[u] = dep[pre] + 1, fa[u] = pre, vis[u] = true;
  for (int i = head[u]; i; i = e[i].link) {
    if (vis[e[i].to]) continue;
    dfs(e[i].to, u);
  }
}
void solve() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) head[i] = 0, vis[i] = false;
  o = 0;
  for (int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), add_edge(u, v);
  dfs(1, 0);
  for (int i = 1; i <= n; i++)
    if (dep[i] >= (n + 1) / 2) {
      puts("PATH");
      printf("%d\n", dep[i]);
      for (; i; i = fa[i]) printf("%d ", i);
      puts("");
      return;
    }
  puts("PAIRING");
  printf("%d\n", m = ((n + 1) / 2 + 1) / 2);
  for (int i = 1; i <= n; i++) lst[i] = 0;
  for (int i = 1; i <= n && m; i++) {
    if (lst[dep[i]])
      printf("%d %d\n", lst[dep[i]], i), lst[dep[i]] = 0, m--;
    else
      lst[dep[i]] = i;
  }
}
int main() {
  scanf("%d", &T);
  while (T--) solve();
}
