#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 10;
void DFS(int x, vector<int> road[], int deep[], int fa[]) {
  for (int i = 0; i < road[x].size(); ++i) {
    int y = road[x][i];
    if (deep[y] == 0) {
      deep[y] = deep[x] + 1;
      fa[y] = x;
      DFS(y, road, deep, fa);
    }
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &n, &m);
    int N = n + 1;
    vector<int> road[N];
    vector<int> cal[N];
    for (int i = 1; i <= n; ++i) {
      cal[i].clear();
    }
    int deep[N];
    int fa[N];
    for (int i = 1; i <= n; ++i) {
      deep[i] = fa[i] = 0;
    }
    int x, y;
    for (int i = 0; i < m; ++i) {
      scanf("%d%d", &x, &y);
      road[x].push_back(y);
      road[y].push_back(x);
    }
    deep[1] = 1;
    fa[1] = 0;
    DFS(1, road, deep, fa);
    int last = 0;
    for (int i = 1; i <= n; ++i) {
      if (deep[i] >= ((n + 1) >> 1)) {
        last = i;
        break;
      }
    }
    if (last != 0) {
      printf("PATH\n");
      printf("%d\n", deep[last]);
      printf("%d", last);
      while (fa[last] != 0) {
        last = fa[last];
        printf(" %d", last);
      }
      printf("\n");
      continue;
    } else {
      int pairs = 0;
      for (int i = 1; i <= n; ++i) {
        int d = deep[i];
        cal[d].push_back(i);
      }
      for (vector<int>& deeplist : cal) {
        pairs += (deeplist.size() >> 1);
      }
      printf("PAIRING\n");
      printf("%d\n", pairs);
      for (vector<int>& deeplist : cal) {
        for (int i = 0; i + 1 < deeplist.size(); i += 2) {
          printf("%d %d\n", deeplist[i], deeplist[i + 1]);
        }
      }
    }
  }
  return 0;
}
