#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF64 = 1e18;
const long long INF32 = 1e9;
const double EPS = static_cast<double>(1e-10);
const double PI = 2.0 * acos(0.0);
const long long MOD = (long long)1e9 + 7;
long long powMod(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
long long invMod(long long a) {
  long long b = MOD, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  return (MOD + u) % MOD;
}
const long long day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
mt19937 rnd(239);
vector<long long> prefixSum(vector<long long> &a) {
  vector<long long> b;
  std::partial_sum(a.begin(), a.end(), b.begin());
  return b;
}
long long mostSignDigit(long long n) {
  double k = log10(n);
  return (long long)pow(10, k - floor(k));
}
long long numOfDigits(long long n) { return (long long)floor(log10(n)) + 1; }
bool isPowerOfTwo(long long x) { return x && (!(x & (x - 1))); }
bool allPositive(vector<long long> &a) {
  return all_of(begin(a), end(a), [](long long x) { return x > 0; });
}
bool anyPositive(vector<long long> &a) {
  return any_of(begin(a), end(a), [](long long x) { return x > 0; });
}
bool nonePositive(vector<long long> &a) {
  return none_of(begin(a), end(a), [](long long x) { return x > 0; });
}
void FILEIO() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
}
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "T" : "F"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
vector<vector<long long>> adj;
vector<long long> lvl;
vector<long long> par;
void dfs(long long vertex) {
  for (long long nxt : adj[vertex]) {
    if (lvl[nxt] == 0) {
      par[nxt] = vertex;
      lvl[nxt] = lvl[vertex] + 1;
      dfs(nxt);
    }
  }
}
void init(long long n) {
  adj.clear();
  adj.assign(n, vector<long long>());
  lvl.clear();
  lvl.resize(n);
  par.clear();
  par.resize(n);
}
void DFS() {
  lvl[0] = 1;
  dfs(0);
}
void solve() {
  long long n, m;
  cin >> n >> m;
  init(n);
  for (long long i = (0); i < (m); i++) {
    long long u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  };
  DFS();
  ;
  ;
  long long mx = -1, umx = 0;
  for (long long u = (0); u < (n); u++) {
    if (lvl[u] > mx) {
      umx = u;
      mx = lvl[u];
    }
  }
  if (mx >= (n + 1) / 2) {
    vector<long long> ans;
    long long u = umx;
    for (long long i = (0); i < (mx); i++) {
      if (((long long)(ans).size()) >= (n + 1) / 2) break;
      ans.push_back(u);
      u = par[u];
    }
    reverse(begin(ans), end(ans));
    cout << "PATH" << endl;
    cout << ((long long)(ans).size()) << endl;
    for (long long i = (0); i < (((long long)(ans).size())); i++)
      cout << ans[i] + 1 << " ";
    cout << endl;
  } else {
    vector<vector<long long>> lvlvec(mx);
    for (long long u = (0); u < (n); u++) lvlvec[lvl[u] - 1].push_back(u);
    ;
    vector<pair<long long, long long>> ans;
    for (long long i = (0); i < (mx); i++) {
      vector<long long> vc = lvlvec[i];
      for (long long j = (0); j < (((long long)(vc).size()) / 2); j++) {
        long long a = vc[2 * j], b = vc[2 * j + 1];
        ans.push_back(make_pair(a, b));
      }
      if (((long long)(ans).size()) * 2 >= (n + 1) / 2) break;
    }
    cout << "PAIRING" << endl;
    cout << ((long long)(ans).size()) << endl;
    for (long long i = (0); i < (((long long)(ans).size())); i++) {
      cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  long long t;
  cin >> t;
  for (long long i = (1); i <= (t); i++) {
    solve();
  }
  return 0;
}
