#include <bits/stdc++.h>
using namespace std;
int32_t seed;
mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
inline int32_t rnd(int32_t l = 0, int32_t r = numeric_limits<int32_t>::max()) {
  return uniform_int_distribution<int32_t>(l, r)(rng);
}
template <typename T, typename G>
ostream& operator<<(ostream& out, const pair<T, G>& a) {
  return out << "( " << a.first << ", " << a.second << ")";
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
  out << "[ ";
  for (const auto& i : a) out << i << ", ";
  return out << "]" << endl;
}
template <typename T>
ostream& operator<<(ostream& out, const set<T>& a) {
  out << "{ ";
  for (const auto& i : a) out << i << ", ";
  return out << "}" << endl;
}
template <typename T, typename G>
ostream& operator<<(ostream& out, const map<T, G>& a) {
  out << "< ";
  for (const auto& i : a) out << i << ", ";
  return out << ">" << endl;
}
template <typename T, size_t N>
typename enable_if<!is_same<typename remove_cv<T>::type, char>::value,
                   ostream&>::type
operator<<(ostream& out, T (&a)[N]) {
  out << "[ ";
  for (const auto& i : a) out << i << ", ";
  return out << "]" << endl;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << (H) << ' ';
  debug_out(T...);
}
vector<vector<int32_t> > adjlst, level;
vector<int32_t> par, vis;
void dfs(int32_t u, int32_t p, int32_t lvl = 0) {
  level[lvl].push_back(u);
  par[u] = p;
  vis[u] = 1;
  for (auto& v : adjlst[u]) {
    if (vis[v]) continue;
    dfs(v, u, lvl + 1);
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int32_t T;
  cin >> T;
  while (T--) {
    int32_t n, m;
    cin >> n >> m;
    adjlst.clear();
    adjlst.resize(n + 1);
    level.clear();
    level.resize(n + 1);
    par.resize(n + 1);
    vis.assign(n + 1, 0);
    for (int32_t i = 0, u, v; i < m; ++i) {
      cin >> u >> v;
      adjlst[u].push_back(v);
      adjlst[v].push_back(u);
    }
    dfs(1, 0);
    if (!level[(n + 1) / 2 - 1].empty()) {
      cout << "PATH\n" << (n + 1) / 2 << '\n';
      int32_t u = level[(n + 1) / 2 - 1][0];
      while (u) {
        cout << u << ' ';
        u = par[u];
      }
      cout << '\n';
    } else {
      int32_t req = (n + 1) / 2;
      cout << "PAIRING\n" << (req + 1) / 2 << '\n';
      for (int32_t i = 0; i < n && req > 0; ++i) {
        for (int32_t j = 1; j < level[i].size() && req > 0; j += 2) {
          cout << level[i][j - 1] << ' ' << level[i][j] << '\n';
          req -= 2;
        }
      }
    }
  }
  return 0;
}
