#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int MAXN = 500005;
const int MOD = 1000000007;
int N, M, h[MAXN], par[MAXN];
vector<int> vec[MAXN];
vector<int> adjList[MAXN];
void dfs(int u, int p) {
  for (auto v : adjList[u]) {
    if (v == p) continue;
    if (h[v] != -1) continue;
    h[v] = h[u] + 1;
    par[v] = u;
    dfs(v, u);
  }
}
void solve() {
  cin >> N >> M;
  for (int i = (0); i <= (N); i++) {
    adjList[i].clear();
    vec[i].clear();
    h[i] = -1;
    par[i] = -1;
  }
  for (int i = (1); i <= (M); i++) {
    int u, v;
    cin >> u >> v;
    adjList[u].push_back(v);
    adjList[v].push_back(u);
  }
  h[1] = 0;
  dfs(1, -1);
  for (int i = (1); i <= (N); i++) {
    vec[h[i]].push_back(i);
    if (h[i] >= (N + 1) / 2) {
      cout << "PATH\n";
      vector<int> path;
      int cur = i;
      path.push_back(cur);
      while (cur != 1) {
        path.push_back(par[cur]);
        cur = par[cur];
      }
      cout << ((int)(path).size()) << "\n";
      for (auto j : path) cout << j << " ";
      cout << "\n";
      return;
    }
  }
  cout << "PAIRING\n";
  vector<pair<int, int> > ans;
  for (int i = (0); i <= (N); i++) {
    while (((int)(vec[i]).size()) >= 2) {
      pair<int, int> tmp;
      tmp.first = vec[i].back();
      vec[i].pop_back();
      tmp.second = vec[i].back();
      vec[i].pop_back();
      ans.push_back(tmp);
    }
  }
  cout << ((int)(ans).size()) << "\n";
  for (auto i : ans) cout << i.first << " " << i.second << "\n";
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int T;
  cin >> T;
  for (int tc = (1); tc <= (T); tc++) solve();
}
