#include <bits/stdc++.h>
using namespace std;
int read() {
  int f = 1, x = 0;
  char c = getchar();
  while (c < '0' || '9' < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return f * x;
}
const int MAXN = 500000;
const int MAXM = 2000000;
const int INF = 0x3f3f3f3f;
struct Edge {
  int v, nxt;
} edge[MAXM + 5];
int ecnt, head[MAXN + 5];
void Addedge(int u, int v) {
  edge[++ecnt] = (Edge){v, head[u]}, head[u] = ecnt;
  edge[++ecnt] = (Edge){u, head[v]}, head[v] = ecnt;
  return;
}
int fa[MAXN + 5];
int dep[MAXN + 5], id;
vector<int> g[MAXN + 5];
void DFS(int u) {
  dep[u] = dep[fa[u]] + 1;
  g[dep[u]].push_back(u);
  if (dep[u] > dep[id]) id = u;
  for (int i = head[u]; i; i = edge[i].nxt) {
    int v = edge[i].v;
    if (!dep[v]) fa[v] = u, DFS(v);
  }
  return;
}
int p1[MAXN + 5], p2[MAXN + 5];
int main() {
  int T = read();
  while (T--) {
    int n = read(), m = read();
    ecnt = 0, fill(head + 1, head + n + 1, 0);
    for (int i = 1; i <= n; i++) g[i].clear(), dep[i] = 0;
    for (int i = 1; i <= m; i++) {
      int u = read(), v = read();
      Addedge(u, v);
    }
    DFS(1);
    int cnt = 0;
    for (int i = 1; i <= dep[id]; i++)
      for (int j = 0; j + 1 < (int)g[i].size(); j += 2)
        p1[++cnt] = g[i][j], p2[cnt] = g[i][j + 1];
    if (cnt * 2 >= (n + 1) / 2) {
      puts("PAIRING");
      printf("%d\n", cnt);
      for (int i = 1; i <= cnt; i++) printf("%d %d\n", p1[i], p2[i]);
      continue;
    }
    puts("PATH"), cnt = 0;
    while (id) p1[++cnt] = id, id = fa[id];
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++)
      printf("%d", p1[i]), putchar(i == cnt ? '\n' : ' ');
  }
  return 0;
}
