#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, deep, goal;
int vis[N];
vector<int> g[N];
vector<int> dfsg[N];
vector<int> ans[N];
stack<int> p;
void getdfs(int u, int d) {
  vis[u] = 1;
  ans[d].push_back(u);
  if (d > deep) {
    deep = d;
    goal = u;
  }
  for (int i = 0; i < (int)g[u].size(); ++i) {
    int v = g[u][i];
    if (!vis[v]) {
      dfsg[u].push_back(v);
      getdfs(v, d + 1);
    }
  }
}
bool path(int u, int goal) {
  if (u == goal) {
    return true;
  }
  for (int i = 0; i < (int)dfsg[u].size(); ++i) {
    int v = dfsg[u][i];
    if (path(v, goal)) {
      p.push(v);
      return true;
    }
  }
  return false;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    while (!p.empty()) p.pop();
    deep = -1;
    scanf("%d%d", &n, &m);
    memset(vis, 0, (n + 1) * (sizeof(int)));
    int limit = ceil(n / 2.0);
    for (int i = 1; i <= n; ++i) g[i].clear(), dfsg[i].clear(), ans[i].clear();
    for (int i = 0; i < m; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      g[u].push_back(v);
      g[v].push_back(u);
    }
    getdfs(1, 1);
    if (deep >= limit) {
      path(1, goal);
      printf("PATH\n%d\n", (int)p.size() + 1);
      printf("1 ");
      while (!p.empty()) {
        printf("%d ", p.top());
        p.pop();
      }
      printf("\n");
    } else {
      int cnt = 1;
      for (int i = 2; i <= deep; ++i) {
        if ((int)ans[i].size() & 1) cnt++;
      }
      printf("PAIRING\n%d\n", (n - cnt) / 2);
      for (int i = 2; i <= deep; ++i) {
        for (int j = 0; j + 1 < (int)ans[i].size(); j += 2) {
          printf("%d %d\n", ans[i][j], ans[i][j + 1]);
        }
      }
    }
  }
}
