#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
void run() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> G(n);
  vector<int> d(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    G[u].push_back(v);
    G[v].push_back(u);
    ++d[u], ++d[v];
  }
  int rt = 0;
  for (int i = 0; i < n; i++)
    if (d[i] > 1) rt = i;
  vector<int> deep(n), up(n), size(n);
  vector<bool> check(n);
  vector<vector<int>> D(n + 1);
  deep[rt] = 1;
  function<void(int, int)> dfs = [&](int u, int fa) {
    D[deep[u]].push_back(u);
    up[u] = fa;
    size[u] = 1;
    check[u] = true;
    for (auto v : G[u])
      if (v != fa && !check[v]) {
        deep[v] = deep[u] + 1;
        dfs(v, u);
        size[u] += size[v];
      }
  };
  dfs(rt, -1);
  int Max = *max_element((deep).begin(), (deep).end());
  if (Max >= (n + 1) / 2) {
    int x = -1;
    for (int i = 0; i < n; i++) {
      if (deep[i] >= (n + 1) / 2) x = i;
    }
    vector<int> path;
    while (x != -1) {
      path.push_back(x);
      x = up[x];
    }
    cout << "PATH" << '\n';
    cout << (int)(path).size() << '\n';
    for (auto& it : path) {
      cout << it + 1 << ' ';
    }
    cout << '\n';
    return;
  }
  vector<pair<int, int>> pairs;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < (int)(D[i]).size(); j += 2) {
      pairs.emplace_back(D[i][j - 1], D[i][j]);
    }
  }
  cout << "PAIRING" << '\n';
  cout << (int)(pairs).size() << '\n';
  for (auto& it : pairs) {
    cout << it.first + 1 << ' ' << it.second + 1 << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(20);
  int T;
  cin >> T;
  while (T--) run();
  return 0;
}
