#include <bits/stdc++.h>
using namespace std;
int n, m, dep[(int)(5e5 + 4)], up[(int)(5e5 + 4)], dist[(int)(5e5 + 4)], mx,
    from[(int)(5e5 + 4)];
vector<int> gtemp[(int)(5e5 + 4)], g[(int)(5e5 + 4)], depth[(int)(5e5 + 4)];
vector<pair<int, int> > ans2;
void read();
void solve();
void dfs(int);
void find(int);
bool CheckPath();
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int q;
  cin >> q;
  for (; q; q--) {
    read();
    solve();
    for (int i = 1; i < n + 1; ++i) {
      g[i].clear();
      gtemp[i].clear();
      depth[i].clear();
      from[i] = 0;
      mx = 0;
      dist[i] = 0;
      up[i] = 0;
      dep[i] = 0;
      ans2.clear();
    }
  }
  return 0;
}
void solve() {
  dep[1] = 1;
  dfs(1);
  if (CheckPath()) return;
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < depth[i].size(); ++j) {
      ans2.push_back({depth[i][j], depth[i][j - 1]});
      ++j;
    }
  }
  cout << "PAIRING\n" << ans2.size() << '\n';
  for (auto it : ans2) cout << it.first << ' ' << it.second << '\n';
  cout << '\n';
}
bool CheckPath() {
  int x = 1;
  for (int i = 1; i < n + 1; ++i)
    if (dep[x] < dep[i]) x = i;
  dist[x] = 1;
  find(x);
  if (dist[mx] >= (n + 1) / 2) {
    vector<int> ans;
    ans.clear();
    while (from[mx] != x) {
      ans.push_back(mx);
      mx = from[mx];
    }
    ans.push_back(mx);
    ans.push_back(x);
    reverse(ans.begin(), ans.end());
    cout << "PATH\n" << ans.size() << '\n';
    for (auto it : ans) cout << it << ' ';
    cout << '\n';
    return 1;
  }
  return 0;
}
void find(int node) {
  if (dist[node] > dist[mx]) mx = node;
  for (auto to : g[node]) {
    if (!dist[to]) {
      dist[to] = dist[node] + 1;
      from[to] = node;
      find(to);
    }
  }
}
void dfs(int node) {
  depth[dep[node]].push_back(node);
  for (auto to : gtemp[node]) {
    if (!dep[to]) {
      dep[to] = dep[node] + 1;
      g[node].push_back(to);
      g[to].push_back(node);
      up[to] = node;
      dfs(to);
    }
  }
}
void read() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    gtemp[x].push_back(y);
    gtemp[y].push_back(x);
  }
}
