#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  write(a);
  puts("");
}
inline void wri(long long a) {
  write(a);
  putchar(' ');
}
long long rnd() {
  unsigned long long ans = 0;
  for (int i = (int)(0); i <= (int)(4); i++) ans = ans << 15 ^ rand();
  return ans % ((unsigned long long)1 << 63);
}
const int N = 500005;
vector<pair<int, int> > ans;
vector<int> v[N], jb[N];
int n, m, rt, dep[N], fa[N], vis[N];
void dfs(int p) {
  if (rt) return;
  dep[p] = dep[fa[p]] + 1;
  vis[p] = 1;
  if (dep[p] >= (n + 1) / 2) {
    rt = p;
    return;
  }
  for (auto i : v[p])
    if (!vis[i]) {
      fa[i] = p;
      dfs(i);
      while (jb[p].size() && jb[i].size()) {
        ans.push_back(make_pair(jb[p].back(), jb[i].back()));
        jb[p].pop_back();
        jb[i].pop_back();
      }
      if (jb[i].size()) swap(jb[p], jb[i]);
    }
  jb[p].push_back(p);
}
int main() {
  int T = read();
  while (T--) {
    n = read();
    m = read();
    rt = 0;
    ans.clear();
    for (int i = (int)(1); i <= (int)(n); i++) {
      v[i].clear();
      jb[i].clear();
      vis[i] = 0;
    }
    for (int i = (int)(1); i <= (int)(m); i++) {
      int s = read(), t = read();
      v[s].push_back(t);
      v[t].push_back(s);
    }
    dfs(1);
    if (rt) {
      vector<int> an;
      for (int i = rt; i; i = fa[i]) an.push_back(i);
      puts("PATH");
      writeln(an.size());
      for (auto i : an) wri(i);
      puts("");
    } else {
      puts("PAIRING");
      writeln(ans.size());
      for (auto i : ans) {
        wri(i.first);
        writeln(i.second);
      }
    }
  }
}
