#include <bits/stdc++.h>
using namespace std;
vector<int> aux;
int n;
bool dfs(int node, vector<bool> &vis, vector<int> &h, vector<vector<int>> &g) {
  vis[node] = 1;
  if (h[node] > (n / 2)) {
    aux.push_back(node);
    return 1;
  }
  for (auto it : g[node]) {
    if (!vis[it]) {
      h[it] = h[node] + 1;
      if (dfs(it, vis, h, g)) {
        aux.push_back(node);
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int ntests;
  cin >> ntests;
  while (ntests--) {
    aux.clear();
    int m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i <= m; i++) {
      int a, b;
      cin >> a >> b;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    vector<bool> vis(n + 1, 0);
    vector<int> h(n + 1, 0);
    h[1] = 1;
    if (dfs(1, vis, h, g)) {
      cout << "PATH\n";
      cout << aux.size() << "\n";
      for (auto it : aux) cout << it << " ";
      cout << "\n";
    } else {
      vector<int> nodes(n + 1, 0);
      vector<pair<int, int>> ans;
      for (int i = 1; i <= n; i++) {
        if (nodes[h[i]] != 0) {
          ans.push_back({i, nodes[h[i]]});
          nodes[h[i]] = 0;
        } else
          nodes[h[i]] = i;
      }
      cout << "PAIRING\n";
      cout << ans.size() << "\n";
      for (auto it : ans) cout << it.first << " " << it.second << "\n";
    }
  }
  return 0;
}
