#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1;
vector<int> g[N], tree[N], nodes[N];
int vis[N], par[N], dep[N];
vector<pair<int, int>> pairs;
vector<int> path;
void dfs(int node, int pa) {
  vis[node] = 1;
  par[node] = pa;
  for (int x : g[node]) {
    if (!vis[x]) {
      tree[node].push_back(x);
      dfs(x, node);
    }
  }
}
int depth(int node) {
  int cur = 0;
  for (int x : tree[node]) {
    cur = max(cur, 1 + depth(x));
  }
  nodes[cur].push_back(node);
  return dep[node] = cur;
}
void find_path(int node) {
  int mx = 0, nx = -1;
  path.push_back(node);
  for (int x : tree[node]) {
    if (dep[x] >= mx) {
      mx = dep[x];
      nx = x;
    }
  }
  if (nx != -1) find_path(nx);
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
      g[i].clear();
      tree[i].clear();
      nodes[i].clear();
      vis[i] = par[i] = dep[i] = 0;
    }
    path.clear();
    pairs.clear();
    for (int i = 0; i < m; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      x--;
      y--;
      g[x].push_back(y);
      g[y].push_back(x);
    }
    dfs(0, -1);
    int d = depth(0);
    int mx = n / 2 + (n % 2 ? 1 : 0);
    if (d + 1 >= mx) {
      printf("PATH\n");
      find_path(0);
      printf("%d\n", path.size());
      for (int x : path) printf("%d ", x + 1);
      printf("\n");
    } else {
      printf("PAIRING\n");
      for (int i = 0; i < mx; i++) {
        for (int j = 1; j < nodes[i].size(); j += 2) {
          pairs.push_back(make_pair(nodes[i][j], nodes[i][j - 1]));
        }
      }
      printf("%d\n", pairs.size());
      for (auto p : pairs) printf("%d %d\n", p.first + 1, p.second + 1);
    }
  }
}
