#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 7;
long long int n, m;
vector<vector<long long int>> adj_list;
vector<bool> vis;
vector<long long int> dep, par;
void dfs(long long int s) {
  vis[s] = true;
  for (auto to : adj_list[s]) {
    if (vis[to]) continue;
    dep[to] = dep[s] + 1;
    par[to] = s;
    dfs(to);
  }
}
void solve() {
  cin >> n >> m;
  adj_list.resize(n + 1, vector<long long int>());
  for (long long int i = 0; i < m; i++) {
    long long int u, v;
    cin >> u >> v;
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
  }
  dep.resize(n + 1, 1);
  par.resize(n + 1, -1);
  vis.resize(n + 1, false);
  for (long long int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i);
    }
  }
  long long int idx = -1;
  long long int mid = ceil(n / 2.0);
  for (long long int i = 1; i <= n; i++) {
    if (dep[i] >= mid) {
      idx = i;
      break;
    }
  }
  if (idx != -1) {
    cout << "PATH\n";
    vector<long long int> path;
    long long int cur = idx;
    while (cur != -1) {
      path.push_back(cur);
      cur = par[cur];
    }
    long long int sz = path.size();
    cout << sz << "\n";
    for (auto it : path) {
      cout << it << " ";
    }
    cout << "\n";
  } else {
    cout << "PAIRING\n";
    vector<vector<long long int>> d(n + 1, vector<long long int>());
    for (long long int i = 1; i <= n; i++) {
      d[dep[i]].push_back(i);
    }
    vector<pair<long long int, long long int>> pairing;
    for (long long int i = 1; i <= n; i++) {
      for (long long int j = 0; j < (int)d[i].size() - 1; j += 2) {
        pairing.push_back({d[i][j], d[i][j + 1]});
      }
    }
    long long int sz = (long long int)pairing.size();
    cout << sz << "\n";
    for (auto it : pairing) {
      cout << it.first << " " << it.second << "\n";
    }
  }
  adj_list.clear();
  dep.clear();
  par.clear();
  vis.clear();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}
