#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long __64inf = 0x3f3f3f3f3f3f3f3f;
const int MAX = 2e6 + 50;
const int mod = 1e9 + 7;
void file_read() {}
vector<int> G[MAX];
bool vis[MAX];
int dep[MAX];
vector<int> dep_set[MAX];
int p[MAX];
int pr[MAX];
void dfs(int u, int parent, int d) {
  dep[u] = d;
  vis[u] = 1;
  p[u] = parent;
  for (auto v : G[u]) {
    if (vis[v]) continue;
    dfs(v, u, d + 1);
  }
}
int main() {
  file_read();
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(vis, 0, sizeof(bool) * (n + 50));
    memset(dep, 0, sizeof(int) * (n + 50));
    memset(p, 0, sizeof(int) * (n + 50));
    for (int i = 1; i <= n; i++) G[i].clear();
    for (int i = 1; i <= n; i++) dep_set[i].clear();
    for (int i = 1; i <= m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    dfs(1, -1, 1);
    int Max = -1, id = -1;
    for (int i = 1; i <= n; i++) {
      if (dep[i] > Max) {
        Max = dep[i];
        id = i;
      }
    }
    if (Max * 2 >= n) {
      puts("PATH");
      vector<int> ans;
      int u = id;
      while (u != -1) {
        ans.push_back(u);
        u = p[u];
      }
      printf("%d\n", ans.size());
      for (auto x : ans) printf("%d ", x);
      puts("");
      continue;
    }
    for (int i = 1; i <= n; i++) {
      dep_set[dep[i]].push_back(i);
    }
    puts("PAIRING");
    vector<pair<int, int> > ans;
    for (int k = 1; k <= Max; k++) {
      for (int i = 0; i + 1 < dep_set[k].size(); i += 2) {
        ans.emplace_back(dep_set[k][i], dep_set[k][i + 1]);
      }
    }
    printf("%d\n", ans.size());
    for (auto p : ans) printf("%d %d\n", p.first, p.second);
  }
  return 0;
}
