#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> graph(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
  vector<int> depth(n, -1);
  vector<int> path;
  function<bool(int, int)> dfs = [&](int v, int l) {
    depth[v] = l;
    if (l >= (n - 1) / 2) {
      path.push_back(v);
      return true;
    }
    for (int ne : graph[v])
      if (depth[ne] < 0 and dfs(ne, l + 1)) {
        path.push_back(v);
        return true;
      }
    return false;
  };
  if (dfs(0, 0)) {
    cout << "PATH\n" << path.size() << "\n";
    for (int v : path) cout << v + 1 << " ";
    cout << "\n";
    return;
  }
  cout << "PAIRING\n";
  vector<pair<int, int>> pairing;
  vector<bool> flags(n);
  vector<int> cand(n);
  for (int v = 0; v < n; v++) {
    if (flags[depth[v]]) {
      pairing.emplace_back(v, cand[depth[v]]);
      flags[depth[v]] = false;
    } else {
      cand[depth[v]] = v;
      flags[depth[v]] = true;
    }
  }
  cout << pairing.size() << "\n";
  for (auto [x, y] : pairing) cout << x + 1 << " " << y + 1 << "\n";
}
signed main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  for (int i = 0; i < tt; i++) solve();
}
