#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 4;
int n, m, par[N], depth[N], pos, vis[N];
vector<int> adj[N], vec[N];
void dfs(int u) {
  vis[u] = 1;
  vec[depth[u]].push_back(u);
  for (auto v : adj[u]) {
    if (vis[v]) continue;
    depth[v] = depth[u] + 1;
    if (depth[v] >= (n + 1) / 2) {
      pos = v;
    }
    par[v] = u;
    dfs(v);
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      adj[i].clear();
      vec[i].clear();
    }
    for (int i = 1; i <= m; i++) {
      int a, b;
      cin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
    par[1] = 0;
    depth[1] = 1;
    pos = 0;
    for (int i = 1; i <= n; i++) vis[i] = 0;
    dfs(1);
    if (pos == 0) {
      int sum = 0;
      for (int i = 1; i <= n; i++) {
        if (vec[i].size() == 0) break;
        sum += (int)vec[i].size() / 2;
      }
      cout << "PAIRING" << '\n';
      cout << sum << '\n';
      for (int i = 1; i <= n; i++) {
        if (vec[i].size() == 0) break;
        for (int j = 0; j + 1 < (int)vec[i].size(); j += 2)
          cout << vec[i][j] << " " << vec[i][j + 1] << '\n';
      }
    } else {
      cout << "PATH" << '\n';
      cout << depth[pos] << '\n';
      while (pos != 0) {
        cout << pos << " ";
        pos = par[pos];
      }
      cout << '\n';
    }
  }
}
