#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int t, n, m, tot, cnt;
struct node {
  int per, to;
} e[1000010 << 1];
int head[1000010];
bool tag[1000010], vis[1000010];
int id[1000010], dis[1000010], f[1000010];
void init() {
  tot = 0, cnt = 0;
  for (int i = 1; i <= n; ++i) {
    head[i] = -1;
    id[i] = dis[i] = tag[i] = f[i] = vis[i] = 0;
  }
}
void addedge(int from, int to) {
  e[++tot].to = to;
  e[tot].per = head[from];
  head[from] = tot;
}
void dfs(int u, int fa, int len) {
  vis[u] = 1;
  f[u] = fa;
  cnt++;
  id[cnt] = u;
  dis[u] = len;
  for (int i = head[u]; i > 0; i = e[i].per) {
    int v = e[i].to;
    if (v == fa || vis[v]) continue;
    dfs(v, u, len + 1);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> t;
  while (t--) {
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; ++i) {
      int x, y;
      cin >> x >> y;
      addedge(x, y);
      addedge(y, x);
    }
    dfs(1, 0, 1);
    bool flag = 0;
    for (int i = 1; i <= n; ++i) {
      if (dis[i] >= (n + 1) / 2) {
        cout << "PATH\n";
        flag = 1;
        cout << dis[i] << "\n";
        int now = i;
        while (now) {
          cout << now << " ";
          now = f[now];
        }
        cout << "\n";
        break;
      }
    }
    if (flag) continue;
    cout << "PAIRING\n";
    int now = id[n - (n + 3) / 4];
    while (now) {
      tag[now] = 1;
      now = f[now];
    }
    now = 1;
    cout << (n - (n - (n + 3) / 4 + 1) + 1) << "\n";
    for (int i = n - (n + 3) / 4 + 1; i <= n; ++i) {
      while (tag[id[now]]) now++;
      cout << id[i] << " " << id[now++] << "\n";
    }
  }
  return 0;
}
