#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& out, vector<T>& v) {
  out << "[";
  for (auto k : v) out << k << " ";
  out << "]"
      << "\n";
  return out;
}
template <class T>
ostream& operator<<(ostream& out, set<T> s) {
  out << "{";
  for (auto k : s) out << k << " ";
  out << "}"
      << "\n";
  return out;
}
template <class T, class U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  out << "[ " << p.first << " , " << p.second << " ] ";
  return out;
}
template <class T, class U>
istream& operator>>(istream& in, pair<T, U>& p) {
  in >> p.first >> p.second;
  return in;
}
const int maxn = 8e5;
int N, M, last[maxn];
bool visto[maxn];
vector<int> g[maxn];
vector<pair<int, int> > pares;
bool listo = false;
void DFS(int nod, vector<int>& cam) {
  if (listo) return;
  if (cam.size() * 2 >= N) {
    cout << "PATH\n";
    cout << cam.size() << "\n";
    for (auto k : cam) cout << k + 1 << " ";
    cout << "\n";
    listo = true;
    return;
  }
  visto[nod] = true;
  if (last[cam.size()] == -1)
    last[cam.size()] = nod;
  else {
    pares.push_back({last[cam.size()], nod});
    last[cam.size()] = -1;
  }
  cam.push_back(nod);
  for (auto k : g[nod])
    if (!visto[k]) DFS(k, cam);
  cam.pop_back();
}
void Caso() {
  listo = false;
  cin >> N >> M;
  for (int i = 0; i < int(N); i++) g[i].clear(), visto[i] = false, last[i] = -1;
  pares.clear();
  for (int i = 0; i < int(M); i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<int> cam;
  DFS(0, cam);
  if (!listo) {
    cout << "PAIRING\n";
    cout << pares.size() << "\n";
    for (auto k : pares) cout << (k.first + 1) << " " << (k.second + 1) << "\n";
  }
}
int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) Caso();
  return 0;
}
