#include <bits/stdc++.h>
using namespace std;
int t, n, m, r1, r2, lay[500005], need, mx, ct;
vector<int> v[500005], ans, ll[500005];
stack<int> st;
bool b;
void f(int x, int last, int l) {
  lay[x] = l;
  ll[l].push_back(x);
  st.push(x);
  mx = max(mx, l);
  if (l >= need && !b) {
    b = true;
    while (st.size()) {
      ans.push_back(st.top());
      st.pop();
    }
  }
  for (int i = 0; i < v[x].size(); i++) {
    if (v[x][i] == last || lay[v[x][i]]) continue;
    f(v[x][i], x, l + 1);
  }
  if (st.size()) st.pop();
  return;
}
void solve() {
  cin >> n >> m;
  need = (n + 1) / 2;
  for (int i = 1; i <= n; i++) {
    v[i].clear();
    ll[i].clear();
    lay[i] = 0;
  }
  ans.clear();
  mx = 0;
  while (st.size()) st.pop();
  for (int i = 1; i <= m; i++) {
    cin >> r1 >> r2;
    v[r1].push_back(r2);
    v[r2].push_back(r1);
  }
  b = false;
  f(1, 0, 1);
  if (b) {
    printf("PATH\n%d\n", (int)ans.size());
    for (int i = 0; i < ans.size(); i++) {
      printf((i == ans.size() - 1) ? "%d\n" : "%d ", ans[i]);
    }
  } else {
    ct = 0;
    for (int i = 1; i <= mx; i++) {
      ct += (ll[i].size() / 2);
    }
    printf("PAIRING\n%d\n", ct);
    for (int i = 1; i <= mx; i++) {
      for (int j = 1; j < ll[i].size(); j += 2) {
        printf("%d %d\n", ll[i][j - 1], ll[i][j]);
      }
    }
  }
  return;
}
int main() {
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
