#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 5;
int n, m;
int read() {
  int x = 0, y = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') y = (ch == '-') ? -1 : 1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * y;
}
int tot = 0, first[M];
struct Edge {
  int nxt, to;
} e[M << 1];
void add(int x, int y) {
  e[++tot] = (Edge){first[x], y};
  first[x] = tot;
}
int de[M], fa[M];
void dfs(int u) {
  for (int i = first[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (de[v]) continue;
    de[v] = de[fa[v] = u] + 1;
    dfs(v);
  }
}
int All, Ans[M][2];
struct Dian {
  int d, f, id;
} d[M];
bool cmp(Dian x, Dian y) { return x.d < y.d; }
void solve() {
  n = read(), m = read();
  tot = 0;
  All = 0;
  for (int i = 1; i <= n; i++) first[i] = de[i] = 0;
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    add(x, y), add(y, x);
  }
  de[1] = 1;
  dfs(1);
  int x = 0;
  for (int i = 1; i <= n; i++)
    if (de[i] > de[x]) x = i;
  if (de[x] >= (n + 1) / 2) {
    printf("PATH\n%d\n", (n + 1) / 2);
    for (int u = x, cnt = 1; cnt <= (n + 1) / 2; u = fa[u], cnt++)
      printf("%d ", u);
    printf("\n");
    return;
  }
  for (int i = 1; i <= n; i++) d[i] = (Dian){de[i], fa[i], i};
  sort(d + 1, d + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    int last = i;
    while (d[i].d == d[i + 1].d) i++;
    for (int j = last; j < i; j += 2) {
      Ans[++All][0] = d[j].id;
      Ans[All][1] = d[j + 1].id;
    }
  }
  printf("PAIRING\n%d\n", All);
  for (int i = 1; i <= All; i++) printf("%d %d\n", Ans[i][0], Ans[i][1]);
}
signed main() {
  int T = read();
  while (T--) solve();
}
