#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("-ffloat-store")
using namespace std;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403() {}
const long long int INF = 0xFFFFFFFFFFFFFFFL;
long long int seed;
mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
inline long long int rnd(long long int l = 0, long long int r = INF) {
  return uniform_int_distribution<long long int>(l, r)(rng);
}
class CMP {
 public:
  bool operator()(pair<long long int, long long int> a,
                  pair<long long int, long long int> b) {
    return !(a.first < b.first || (a.first == b.first && a.second <= b.second));
  }
};
void add(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt == m.end())
    m.insert({x, cnt});
  else
    jt->second += cnt;
}
void del(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt->second <= cnt)
    m.erase(jt);
  else
    jt->second -= cnt;
}
bool cmp(const pair<long long int, long long int> &a,
         const pair<long long int, long long int> &b) {
  return a.first < b.first || (a.first == b.first && a.second < b.second);
}
const long long int mod = 1000000007L;
long long int T, n, i, j, k, in, cnt, l, r, u, v, x, y;
long long int m;
string s;
vector<vector<long long int> > e;
vector<long long int> hh, par;
vector<pair<long long int, long long int> > prs;
long long int L;
bool fl;
void moveup(long long int u) {
  if (fl) return;
  cout << "PATH"
       << "\n";
  cout << L << "\n";
  while (u) {
    cout << u << " ";
    u = par[u];
  }
  cout << "\n";
  fl = true;
}
void dfs(long long int u, long long int h) {
  if (fl) return;
  if (h >= L) moveup(u);
  if (hh[h] == -1)
    hh[h] = u;
  else {
    prs.push_back({hh[h], u});
    hh[h] = -1;
  }
  for (auto x : e[u]) {
    if (par[x] != -1) continue;
    par[x] = u;
    ;
    dfs(x, h + 1);
  }
}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> T;
  while (T--) {
    cin >> n >> m;
    fl = false;
    assert(m >= 1);
    e.clear();
    prs.clear();
    hh.clear();
    par.clear();
    e.resize(n + 1);
    L = (n + 1) / 2;
    for (i = 0; i < (m); ++i) {
      cin >> u >> v;
      e[u].push_back(v);
      e[v].push_back(u);
    };
    par.resize(n + 1, -1);
    hh.resize(n + 1, -1);
    par[1] = 0;
    dfs(1, 1);
    if (!fl) {
      cout << "PAIRING"
           << "\n";
      assert(2 * ((long long int)(prs).size()) >= L);
      cout << ((long long int)(prs).size()) << "\n";
      for (auto x : prs) cout << x.first << " " << x.second << "\n";
    }
  }
  aryanc403();
  return 0;
}
