#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long inf = 1LL << 50;
const int N = 500000;
int mx;
int parents[N];
bool visited[N];
void dfs(int curr, vector<vector<int>>& levels, vector<vector<int>>& graph,
         int depth) {
  levels[depth].push_back(curr);
  mx = max(mx, depth);
  visited[curr] = true;
  for (int i : graph[curr]) {
    if (!visited[i]) {
      parents[i] = curr;
      dfs(i, levels, graph, depth + 1);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin.exceptions(cin.failbit);
  int t;
  cin >> t;
  for (int z = 0; z < t; z++) {
    int n, m;
    cin >> n >> m;
    fill(visited, visited + n, false);
    vector<vector<int>> graph(n);
    vector<vector<int>> levels(n + 1);
    parents[0] = -1;
    mx = 1;
    for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      a--;
      b--;
      graph[a].push_back(b);
      graph[b].push_back(a);
    }
    dfs(0, levels, graph, 1);
    int k = (n + 1) / 2;
    if (mx >= k) {
      cout << "PATH\n" << k << "\n";
      int curr = levels[k][0];
      while (curr != 0) {
        cout << curr + 1 << " ";
        curr = parents[curr];
      }
      cout << 1 << "\n";
    } else {
      cout << "PAIRING\n";
      vector<pair<int, int>> pairs;
      for (int l = 1; l <= mx; l++) {
        for (int i = 1; i < levels[l].size(); i += 2) {
          pairs.push_back({levels[l][i - 1] + 1, levels[l][i] + 1});
        }
      }
      cout << pairs.size() << "\n";
      for (pair<int, int> i : pairs) {
        cout << i.first << " " << i.second << "\n";
      }
    }
  }
}
