#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const long long inf = 1ll << 62;
const int iinf = 0x7fffffff;
long long powmod(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans *= a;
      ans %= mod;
    }
    b >>= 1;
    a *= a;
    a %= mod;
  }
  return ans;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; };
int n, m;
vector<vector<int> > g;
vector<vector<int> > anspair;
vector<int> anspath;
vector<bool> visit;
bool path = false;
void dfs(int u, int d) {
  if (path) return;
  visit[u] = 1;
  anspath.push_back(u);
  anspair[d].push_back(u);
  if (anspath.size() >= (n + 1) / 2) {
    cout << "PATH" << endl;
    cout << anspath.size() << endl;
    for (int i : anspath) cout << i << " ";
    cout << endl;
    path = true;
    return;
  }
  for (int i : g[u])
    if (!visit[i]) dfs(i, d + 1);
  anspath.pop_back();
}
void solve() {
  path = false;
  anspair.clear();
  g.clear();
  anspath.clear();
  cin >> n >> m;
  visit.assign(n + 1, 0);
  g.resize(n + 1);
  anspair.resize(n + 1);
  for (int(i) = (0); (i) < (m); (i)++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1, 0);
  if (path) return;
  cout << "PAIRING" << endl;
  vector<pair<int, int> > ansp;
  for (int(i) = (0); (i) < (n); (i)++) {
    if (anspair[i].size() == 0) break;
    int len = anspair[i].size();
    for (int j = 0; j < len - 1; j += 2) {
      ansp.push_back(make_pair(anspair[i][j], anspair[i][j + 1]));
    }
  }
  cout << ansp.size() << endl;
  for (pair<int, int> i : ansp) {
    cout << i.first << " " << i.second << endl;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  cin >> T;
  while (T--) solve();
  return 0;
}
