#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using f64 = double;
using f80 = long double;
using pii = pair<int, int>;
using ptx = pair<f64, f64>;
const int N = 5e5 + 5;
bool f[N];
vector<int> g[N], onlvl[N];
vector<int> path, path_ans;
int n, m, dep;
static void dfs(int u) {
  path.push_back(u);
  onlvl[path.size()].push_back(u);
  dep = max(dep, int(path.size()));
  f[u] = true;
  if (path.size() >= (n + 1) / 2)
    if (path_ans.empty()) path_ans = path;
  for (auto v : g[u])
    if (!f[v]) dfs(v);
  path.pop_back();
}
static void solve() {
  cin >> n >> m;
  for (int a, b, i = 0; i < m; ++i) {
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1);
  if (path_ans.empty()) {
    cout << "PAIRING\n";
    vector<pii> ans;
    ans.reserve(n);
    for (int l = 1; l <= dep; ++l)
      for (int i = 1; i < onlvl[l].size(); i += 2)
        ans.emplace_back(onlvl[l][i - 1], onlvl[l][i]);
    cout << ans.size() << '\n';
    for (auto i : ans) cout << i.first << ' ' << i.second << '\n';
  } else {
    cout << "PATH\n";
    cout << path_ans.size() << '\n';
    for (auto i : path_ans) cout << i << ' ';
    cout << '\n';
  }
}
static void clean() {
  for (int i = 1; i <= n; ++i) {
    g[i].clear();
    onlvl[i].clear();
    f[i] = false;
  }
  dep = 0;
  path.clear();
  path_ans.clear();
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int tsk;
  cin >> tsk;
  while (tsk--) {
    solve();
    if (tsk > 0) clean();
  }
  return 0;
}
