#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
void deb(initializer_list<T> l) {
  for (auto& e : l) cout << e << ' ';
  cout << endl;
}
int n, m;
vector<vector<int>> adj, tree;
vector<bool> vis;
void dfs0(int u, int d, int& maxd, int& end1) {
  vis[u] = true;
  if (d > maxd) {
    maxd = d;
    end1 = u;
  }
  for (auto& v : adj[u]) {
    if (!vis[v]) {
      tree[u].push_back(v);
      tree[v].push_back(u);
      dfs0(v, d + 1, maxd, end1);
    }
  }
}
vector<int> p;
int diameter;
void dfs(int u, int par, int d, int& end2) {
  if (d > diameter) {
    diameter = d;
    end2 = u;
  }
  p[u] = par;
  for (auto& v : adj[u])
    if (v != par) dfs(v, u, d + 1, end2);
}
void printPath(int v, int u) {
  vector<int> path{v};
  path.reserve(n);
  while (v != u) {
    v = p[v];
    path.push_back(v);
  }
  cout << "PATH\n" << path.size() << '\n';
  for (auto& e : path) cout << e + 1 << ' ';
  cout << '\n';
}
vector<vector<int>> d;
void dfs(int u, int p, int dist) {
  assert(dist < (n + 1) / 2);
  d[dist].push_back(u);
  for (auto& v : adj[u])
    if (v != p) dfs(v, u, dist + 1);
}
void solve() {
  cin >> n >> m;
  adj.assign(n, {});
  tree.assign(n, {});
  while (m--) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    adj[u].push_back(v);
    swap(u, v);
    adj[u].push_back(v);
  }
  vis.assign(n, false);
  int end1 = -1;
  int maxd = 0;
  dfs0(0, 0, maxd, end1);
  swap(adj, tree);
  p.resize(n);
  int end2 = -1;
  diameter = 0;
  dfs(end1, -1, 0, end2);
  if (diameter >= (n + 1) / 2) {
    printPath(end2, end1);
    return;
  }
  d.assign(n, {});
  dfs(0, -1, 0);
  vector<pair<int, int>> ans;
  ans.reserve(n);
  for (int dist = 0; dist < n; ++dist)
    for (int i = 0; i + 1 < (int)d[dist].size(); i += 2)
      ans.push_back({d[dist][i] + 1, d[dist][i + 1] + 1});
  cout << "PAIRING\n" << ans.size() << '\n';
  for (auto& [u, v] : ans) cout << u << ' ' << v << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}
