#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  auto solve = [&]() {
    int n, m;
    cin >> n >> m;
    vector<bool> visited(n, false);
    vector<vector<int>> adjacenyList(n);
    vector<int> depth(n, 0), parent(n, -1);
    while (m--) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      adjacenyList[u].emplace_back(v);
      adjacenyList[v].emplace_back(u);
    }
    function<void(int)> DepthFirstSearch = [&](int u) {
      visited[u] = true;
      for (int &v : adjacenyList[u]) {
        if (!visited[v]) {
          depth[v] = depth[u] + 1;
          parent[v] = u;
          DepthFirstSearch(v);
        }
      }
    };
    DepthFirstSearch(0);
    for (int u = 0; u < n; u++) {
      if (depth[u] + 1 >= (n + 1) / 2) {
        vector<int> path;
        do {
          path.emplace_back(u);
          u = parent[u];
        } while (u != -1);
        cout << "PATH\n";
        cout << path.size() << '\n';
        for (auto &u : path) cout << ++u << ' ';
        cout << '\n';
        return;
      }
    }
    vector<vector<int>> NodeAtDepth(n);
    for (int u = 0; u < n; u++) NodeAtDepth[depth[u]].emplace_back(u);
    vector<pair<int, int>> pairings;
    for (int d = 0; d < n; d++) {
      if (NodeAtDepth[d].size() < 2) continue;
      for (int i = 0; i < NodeAtDepth[d].size() - 1; i += 2) {
        pairings.emplace_back(NodeAtDepth[d][i], NodeAtDepth[d][i + 1]);
      }
    }
    cout << "PAIRING\n";
    cout << pairings.size() << '\n';
    for (auto &pairing : pairings) {
      int u, v;
      tie(u, v) = pairing;
      cout << ++u << ' ' << ++v << '\n';
    }
  };
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
