#include <bits/stdc++.h>
std::mt19937_64 mersenne_twister(
    std::chrono::steady_clock::now().time_since_epoch().count());
void solve() {
  int vertices, e;
  scanf("%d %d", &vertices, &e);
  std::vector<std::vector<int>> edges(vertices);
  for (int i = 0; i < e; i++) {
    int v1, v2;
    scanf("%d %d", &v1, &v2);
    v1--, v2--;
    edges[v1].push_back(v2);
    edges[v2].push_back(v1);
  }
  std::vector<int> parents(vertices, -1), degree(vertices, -1);
  std::vector<std::vector<int>> childs(vertices);
  std::vector<std::vector<int>> crossedges(vertices);
  int root = 0;
  std::vector<std::pair<int, int>> stack = {{root, -1}};
  std::vector<bool> visited(vertices, false);
  while (!stack.empty()) {
    auto info = stack.back();
    stack.pop_back();
    int prev = info.second, now = info.first;
    if (visited[now]) continue;
    visited[now] = true;
    parents[now] = prev;
    degree[now] = (parents[now] == -1 ? 0 : degree[parents[now]] + 1);
    for (int neighbor : edges[now]) {
      if (neighbor == prev)
        continue;
      else if (!visited[neighbor])
        stack.push_back({neighbor, now});
      else
        crossedges[now].push_back(neighbor);
    }
  }
  for (int now = 0; now < vertices; now++) -1;
  int maxdegree = 0, deepest = -1;
  for (int now = 0; now < vertices; now++)
    if (degree[now] > maxdegree) maxdegree = degree[now], deepest = now;
  if (maxdegree >= (vertices - 1) / 2) {
    std::vector<int> path = {deepest};
    while (true) {
      if (parents[path.back()] == -1)
        break;
      else
        path.push_back(parents[path.back()]);
    }
    printf("PATH\n%d\n", (int)path.size());
    for (int num : path) printf("%d ", num + 1);
    printf("\n");
  } else {
    std::vector<std::pair<int, int>> pairs;
    std::vector<std::vector<int>> vertices_by_degree(maxdegree + 1);
    for (int now = 0; now < vertices; now++)
      vertices_by_degree[degree[now]].push_back(now);
    for (int depth = 0; depth <= maxdegree; depth++) {
      while ((int)vertices_by_degree[depth].size() > 1) {
        int v1 = vertices_by_degree[depth].back();
        vertices_by_degree[depth].pop_back();
        int v2 = vertices_by_degree[depth].back();
        vertices_by_degree[depth].pop_back();
        pairs.push_back({v1, v2});
      }
    }
    printf("PAIRING\n%d\n", (int)pairs.size());
    for (auto pair : pairs) printf("%d %d\n", pair.first + 1, pair.second + 1);
  }
}
int main(int argc, char **argv) {
  int t;
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}
