#include <bits/stdc++.h>
using namespace std;
const int N = 500100, M = 4000010;
int n, m;
int d[N], vis[N], maxd, fa[N], s[N], maxi;
vector<int> dv[N], mp[N];
void dfs(int u) {
  for (int i = 0; i < mp[u].size(); i++) {
    int v = mp[u][i];
    if (!vis[v]) {
      d[v] = d[u] + 1;
      dv[d[v]].push_back(v);
      if (maxd < d[v]) {
        maxi = v;
        maxd = d[v];
      }
      fa[v] = u;
      vis[v] = 1;
      dfs(v);
    }
  }
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    maxd = 0;
    for (int i = 1; i <= n; i++) {
      d[i] = vis[i] = 0;
      dv[i].clear();
      mp[i].clear();
    }
    int u, v;
    for (int i = 1; i <= m; i++) {
      scanf("%d%d", &u, &v);
      mp[u].push_back(v);
      mp[v].push_back(u);
    }
    d[1] = 1;
    vis[1] = 1;
    dfs(1);
    if (maxd > (n / 2 + ((n % 2) ? 1 : 0))) {
      cout << "PATH" << endl;
      cout << maxd << endl;
      int top = 1;
      for (int i = maxi; i != 1; i = fa[i]) s[top++] = i;
      cout << 1 << ' ';
      top--;
      while (top > 0) cout << s[top--] << ' ';
      cout << endl;
    } else {
      cout << "PAIRING" << endl;
      int ans = 0;
      for (int i = 2; i <= maxd; i++) ans += (dv[i].size() / 2);
      cout << ans << endl;
      for (int i = 2; i <= maxd; i++)
        for (int j = 1; j < dv[i].size(); j += 2)
          cout << dv[i][j - 1] << ' ' << dv[i][j] << endl;
    }
  }
}
