#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int t, n, m, dep[500010];
vector<int> e[500010], levels[500010];
vector<int> path, pans;
bool vis[500010];
void dfs(int node, int depth) {
  vis[node] = true;
  dep[node] = depth;
  levels[depth].push_back(node);
  if (dep[node] >= (n + 1) / 2 && pans.empty()) pans = path;
  for (int ch : e[node]) {
    if (vis[ch]) continue;
    path.push_back(ch);
    dfs(ch, depth + 1);
    path.pop_back();
  }
}
void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) e[i].clear(), vis[i] = false, levels[i].clear();
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    e[x].push_back(y), e[y].push_back(x);
  }
  path = {1}, pans.clear();
  dfs(1, 1);
  if (!pans.empty()) {
    cout << "PATH" << endl << pans.size() << endl;
    for (int xx : pans) cout << xx << " ";
    cout << endl;
  } else {
    vector<pair<int, int>> ans;
    for (int d = 2; d <= n && !levels[d].empty(); ++d) {
      for (int i = 1; i < (int)levels[d].size(); i += 2) {
        ans.push_back({levels[d][i], levels[d][i - 1]});
      }
    }
    cout << "PAIRING" << endl << ans.size() << endl;
    for (auto xx : ans) cout << xx.first << " " << xx.second << endl;
  }
}
int main() {
  ios::sync_with_stdio(false);
  for (cin >> t; t--;) solve();
  return 0;
}
