#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma GCC optimize(3)
template <typename T>
T min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T max(T x, T y) {
  return x > y ? x : y;
};
const int INF = 2000000005;
const int MAXN = 1000005;
struct node {
  int v;
  node *next;
  node() {
    v = 0;
    next = NULL;
  }
};
void addnode(node *&p, int to) {
  node *t = new node;
  t->v = to;
  t->next = p;
  p = t;
}
void del(node *&p) {
  while (p) {
    node *t = p->next;
    delete p;
    p = t;
  }
}
int N, M;
node *edge[MAXN];
int dep[MAXN], fa[MAXN];
std::vector<int> V[MAXN];
void dfs(int v) {
  dep[v] = dep[fa[v]] + 1;
  V[dep[v]].push_back(v);
  for (node *p = edge[v]; p; p = p->next) {
    if (dep[p->v]) continue;
    fa[p->v] = v;
    dfs(p->v);
  }
}
void solve() {
  int u, v;
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= M; i++) {
    scanf("%d %d", &u, &v);
    addnode(edge[u], v);
    addnode(edge[v], u);
  }
  dfs(1);
  bool flag = 0;
  for (int i = 1; i <= N; i++) {
    if (dep[i] >= (N + 1) / 2) {
      flag = 1;
      printf("PATH\n");
      printf("%d\n", dep[i]);
      for (int t = i; t; t = fa[t]) printf("%d\n", t);
      break;
    }
  }
  if (!flag) {
    int cnt = N;
    for (int i = 1; i <= N; i++) cnt -= (V[i].size() & 1);
    printf("PAIRING\n%d\n", cnt / 2);
    for (int i = 1; i <= N; i++)
      for (int j = 1; j * 2 <= V[i].size(); j++)
        printf("%d %d\n", V[i][j * 2 - 2], V[i][j * 2 - 1]);
  }
  for (int i = 1; i <= N; i++) {
    dep[i] = fa[i] = 0;
    del(edge[i]);
    V[i].clear();
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}
