#include <bits/stdc++.h>
#pragma GCC optimize("fast-math")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC diagnostic ignored "-Woverflow"
using namespace std;
const short INF16 = ~(1 << 15);
const int INF32 = 2e9 + 11;
const int SZ = 4e5 + 11;
const int SZ2 = int(1e6 + 11);
const int mod = 1e9 + 7;
const int mod2 = 998244353;
const int PIVO = 1e6 + 11;
const long long INF64 = 8e18;
const long long P1 = 53;
const long long P2 = 47;
const long double eps = 1e-10;
const long double PI = acosl(-1);
inline long long MOD(long long x) {
  x %= mod, x += mod;
  return x % mod;
}
inline long long MOD(long long x, long long m) {
  x %= m, x += m;
  return x % m;
}
inline long long T(int x) { return 1ll * x * (x + 1) >> 1; }
inline long long TT(int x) { return 1ll * x * (x + 1) * (x + 2) / 6; }
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
long long fpow(long long a, long long b, long long mod) {
  if (!b) return 1;
  if (b == 1) return a % mod;
  if (b & 1) return fpow(a, b ^ 1, mod) * a % mod;
  long long d = fpow(a, b >> 1, mod);
  return d * d % mod;
}
long long fpow(long long a, long long b) {
  if (!b) return 1;
  if (b == 1) return a;
  if (b & 1) return fpow(a, b ^ 1) * a;
  long long d = fpow(a, b >> 1);
  return d * d;
}
vector<vector<int>> g;
vector<int> h, p;
int n;
void dfs(int v, int& finish, int pp = 0, int hh = 1) {
  h[v] = hh;
  p[v] = pp;
  if (h[v] >= (n + 1) / 2) finish = v;
  for (int u : g[v])
    if (!h[u]) dfs(u, finish, v, hh + 1);
}
void Solve(int num_test) {
  int m;
  cin >> n >> m;
  g.clear();
  h.clear();
  p.clear();
  g.resize(n + 1);
  h.resize(n + 1);
  p.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int v, u;
    cin >> v >> u;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  int finish = -1;
  dfs(1, finish);
  if (finish == -1) {
    vector<vector<int>> cnt((n + 1) / 2 + 1);
    vector<pair<int, int>> ans;
    for (int v = 1; v <= n; v++) cnt[h[v]].push_back(v);
    for (int hh = 1; hh <= (n + 1) / 2; hh++) {
      while (cnt[hh].size() >= 2) {
        pair<int, int> kek = {cnt[hh][cnt[hh].size() - 1],
                              cnt[hh][cnt[hh].size() - 2]};
        cnt[hh].erase(cnt[hh].begin() + cnt[hh].size() - 1);
        cnt[hh].erase(cnt[hh].begin() + cnt[hh].size() - 1);
        ans.push_back(kek);
      }
    }
    cout << "PAIRING\n" << ans.size() << '\n';
    for (auto x : ans) cout << x.first << ' ' << x.second << '\n';
  } else {
    cout << "PATH\n";
    int pp = finish;
    vector<int> ans = {};
    while (pp) {
      ans.push_back(pp);
      pp = p[pp];
    }
    cout << ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
    cout << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(NULL);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed << setprecision(10);
  srand(time(NULL));
  int test = 1;
  cin >> test;
  for (int i = 1; i <= test; i++) Solve(i);
}
