#include <bits/stdc++.h>
using namespace std;
template <class A, class B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
  return out << "(" << p.first << ", " << p.second << ")";
}
template <class A>
ostream& operator<<(ostream& out, const vector<A>& v) {
  out << "[";
  for (long long i = 0; i < v.size(); i++) {
    if (i) out << ", ";
    out << v[i];
  }
  return out << "]";
}
template <class A, class B>
ostream& operator<<(ostream& out, const set<A, B>& s) {
  out << "[";
  for (auto i = s.begin(); i != s.end(); i++) {
    out << ", ";
    out << *i;
  }
  return out << "]";
}
template <class A>
ostream& operator<<(ostream& out, const set<A>& s) {
  out << "[";
  for (auto i = s.begin(); i != s.end(); i++) {
    out << ", ";
    out << *i;
  }
  return out << "]";
}
const long long N = 5e5 + 10;
long long mark[N];
vector<long long> G[N];
vector<long long> T[N];
long long deep[N];
long long par[N];
vector<long long> vertics_with_same_deep[N];
void graph_dfs(long long u) {
  mark[u] = 1;
  for (auto v : G[u]) {
    if (mark[v] == 0) {
      T[u].push_back(v);
      par[v] = u;
      graph_dfs(v);
    }
  }
}
void tree_dfs(long long u) {
  mark[u] = 1;
  for (auto v : G[u]) {
    if (mark[v] == 0) {
      deep[v] = deep[u] + 1;
      vertics_with_same_deep[deep[v]].push_back(v);
      tree_dfs(v);
    }
  }
}
void print_path(long long u) {
  cout << u << " ";
  if (u == 1) {
    return;
  }
  print_path(par[u]);
}
void myMain() {
  long long n, m;
  cin >> n >> m;
  long long k = n - n / 2;
  for (long long i = 0; i <= n + 4; i++) {
    G[i].clear();
    T[i].clear();
    vertics_with_same_deep[i].clear();
  }
  for (long long i = 0; i < m; i++) {
    long long u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  fill(mark, mark + n + 1, 0);
  fill(deep, deep + n + 1, 0);
  fill(par, par + n + 1, 0);
  graph_dfs(1);
  fill(mark, mark + n + 1, 0);
  tree_dfs(1);
  vector<pair<long long, long long> > ans;
  ans.clear();
  if (vertics_with_same_deep[k - 1].size() > 0) {
    long long u = vertics_with_same_deep[k - 1][0];
    cout << "PATH" << endl << k << endl;
    print_path(u);
    cout << endl;
    return;
  } else {
    for (long long i = 1; vertics_with_same_deep[i].size() >= 1; i++) {
      if (vertics_with_same_deep[i].size() == 1) continue;
      for (long long j = 1; j < vertics_with_same_deep[i].size(); j += 2) {
        ans.push_back(pair<long long, long long>(
            vertics_with_same_deep[i][j], vertics_with_same_deep[i][j - 1]));
      }
    }
    cout << "PAIRING" << endl << ans.size() << endl;
    for (auto p : ans) {
      cout << p.first << " " << p.second << endl;
    }
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    myMain();
  }
  return 0;
}
