#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
  return x;
}
const int N = 1000006;
struct node {
  int y, nxt;
} e[N << 1];
int tot = 0, h[N];
void ad(int x, int y) {
  ++tot;
  e[tot].y = y;
  e[tot].nxt = h[x];
  h[x] = tot;
  ++tot;
  e[tot].y = x;
  e[tot].nxt = h[y];
  h[y] = tot;
}
int t, n, m;
int vis[N], dep[N], mxdep = 1;
vector<int> flo[N];
void dfs(int x) {
  mxdep = max(mxdep, dep[x]);
  flo[dep[x]].push_back(x);
  for (int i = h[x]; i; i = e[i].nxt) {
    int y = e[i].y;
    if (dep[y]) continue;
    vis[y] = 1;
    dep[y] = dep[x] + 1;
    dfs(y);
  }
}
bool draw(int x) {
  if (dep[x] == mxdep) {
    printf("%d ", x);
    return true;
  }
  int flag = 0;
  for (int i = h[x]; i; i = e[i].nxt) {
    int y = e[i].y;
    if (dep[y] != dep[x] + 1) continue;
    flag = draw(y);
    if (flag) {
      printf("%d ", x);
      return true;
    }
  }
  return false;
}
int main() {
  t = read();
  while (t--) {
    tot = 0;
    n = read();
    m = read();
    int x, y;
    for (int i = 1; i <= m; ++i) {
      x = read();
      y = read();
      ad(x, y);
    }
    vis[1] = 1;
    dep[1] = 1;
    mxdep = 1;
    dfs(1);
    if (mxdep >= (n + 1) / 2) {
      puts("PATH");
      printf("%d\n", mxdep);
      draw(1);
      puts(" ");
    } else {
      puts("PAIRING");
      int cnt = 0;
      for (int i = 2; i <= n / 2; ++i) {
        int len = flo[i].size();
        if (len % 2) --len;
        cnt += len / 2;
      }
      printf("%d\n", cnt);
      for (int i = 2; i <= n / 2; ++i) {
        int len = flo[i].size();
        if (len % 2) --len;
        for (int j = 0; j < len; j += 2) {
          printf("%d %d\n", flo[i][j], flo[i][j + 1]);
        }
      }
    }
    for (int i = 2; i <= mxdep; ++i) {
      flo[i].clear();
    }
    for (int i = 1; i <= n; ++i) {
      dep[i] = vis[i] = h[i] = 0;
    }
  }
}
