Problem: You have a simple and connected undirected graph consisting of n nodes and m edges.

Consider any way to pair some subset of these n nodes such that no node is present in more than one pair. 

This pairing is valid if for every pair of pairs, the induced subgraph containing all 4 nodes, two from each pair, has at most 2 edges (out of the 6 possible edges). More formally, for any two pairs, (a,b) and (c,d), the induced subgraph with nodes \\{a,b,c,d\} should have at most 2 edges. 

Please note that the subgraph induced by a set of nodes contains nodes only from this set and edges which have both of its end points in this set.

Now, do one of the following: 

  * Find a simple path consisting of at least ⌈ n/2 ⌉ nodes. Here, a path is called simple if it does not visit any node multiple times. 
  * Find a valid pairing in which at least ⌈ n/2 ⌉ nodes are paired. 



It can be shown that it is possible to find at least one of the two in every graph satisfying constraints from the statement. 

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^5). Description of the test cases follows.

The first line of each test case contains 2 integers n, m (2 ≤ n ≤ 5⋅ 10^5, 1 ≤ m ≤ 10^6), denoting the number of nodes and edges, respectively. 

The next m lines each contain 2 integers u and v (1 ≤ u, v ≤ n, u ≠ v), denoting that there is an undirected edge between nodes u and v in the given graph.

It is guaranteed that the given graph is connected, and simple — it does not contain multiple edges between the same pair of nodes, nor does it have any self-loops. 

It is guaranteed that the sum of n over all test cases does not exceed 5⋅ 10^5.

It is guaranteed that the sum of m over all test cases does not exceed 10^6.

Output

For each test case, the output format is as follows. 

If you have found a pairing, in the first line output "PAIRING" (without quotes). 

  * Then, output k (⌈ n/2 ⌉ ≤ 2⋅ k ≤ n), the number of pairs in your pairing. 
  * Then, in each of the next k lines, output 2 integers a and b — denoting that a and b are paired with each other. Note that the graph does not have to have an edge between a and b!
  * This pairing has to be valid, and every node has to be a part of at most 1 pair. 



Otherwise, in the first line output "PATH" (without quotes). 

  * Then, output k (⌈ n/2 ⌉ ≤ k ≤ n), the number of nodes in your path. 
  * Then, in the second line, output k integers, v_1, v_2, …, v_k, in the order in which they appear on the path. Formally, v_i and v_{i+1} should have an edge between them for every i (1 ≤ i < k).
  * This path has to be simple, meaning no node should appear more than once. 

Example

Input


4
6 5
1 4
2 5
3 6
1 5
3 5
6 5
1 4
2 5
3 6
1 5
3 5
12 14
1 2
2 3
3 4
4 1
1 5
1 12
2 6
2 7
3 8
3 9
4 10
4 11
2 4
1 3
12 14
1 2
2 3
3 4
4 1
1 5
1 12
2 6
2 7
3 8
3 9
4 10
4 11
2 4
1 3


Output


PATH
4 
1 5 3 6
PAIRING
2
1 6
2 4
PAIRING
3
1 8
2 5
4 10
PAIRING
4
1 7
2 9
3 11
4 5

Note

The path outputted in the first case is the following. 

<image>

The pairing outputted in the second case is the following. 

<image>

Here is an invalid pairing for the same graph — the subgraph \{1,3,4,5\} has 3 edges. 

<image>

Here is the pairing outputted in the third case. 

<image>

It's valid because — 

  * The subgraph \{1,8,2,5\} has edges (1,2) and (1,5). 
  * The subgraph \{1,8,4,10\} has edges (1,4) and (4,10). 
  * The subgraph \{4,10,2,5\} has edges (2,4) and (4,10). 



Here is the pairing outputted in the fourth case. 

<image>

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.Math;
import java.util.*;

public class Main  {

    public BufferedReader in;
    public PrintStream out;

    public boolean log_enabled = false;
    
    public boolean multiply_tests = true;
    
    public void gen_tests(){
        
            int T = 1000;
            
            int N = 2000;
        
            out.println(T);
            
            for (int t=0; t<T; t++)
            {
                out.printf("%d %d\n", N, 2*N-3);
                out.println("1 2");
                for (int i=3; i<=N; i++)
                {
                    out.printf("%d %d\n", 1, i);
                    out.printf("%d %d\n", 2, i);
                }
            }
            
            
        }

    private class TestCase {

        int N;
        int[] adj_count;
        int[][] adj_list;
        
        int lv_count = 0;
        int[] lv_list;
        
        int max_path = 0;
        
        int[] prev;
        int[] u1;
        int[] u2;
        int root;
        
        boolean[] visited;
        
        int[] D;
        
        public int dfs(int u, int p, int d)
        {
            visited[u] = true;
            D[u] = d;
            prev[u] = p;
            int v = 0, d1=0, d2=0, c;
            
            u1[u] = u;
            u2[u] = u;
            
            for (int i=0; i<adj_count[u]; i++)
            {
                v = adj_list[u][i];
                if (!visited[v])
                {
                    c = dfs(v, u, d+1);
                    if (c>d1)
                    {
                        u2[u] = u1[u];
                        u1[u] = u1[v];
                        
                        d2 = d1;
                        d1 = c;
                    }
                    else if (c>d2)
                    {
                        u2[u] = u1[v];
                        d2 = c;
                    }
                }
            }
            
            if (d1+d2+1 > max_path)
            {
                max_path = d1+d2+1;
                root = u;
            }
            
            return d1+1;
        }
        
        public Object solve() {
            
            N = readInt();
            int m = readInt();
            
            
            
            adj_count = new int[N];
            adj_list = new int[N][];
            
            Arrays.fill(adj_count, 0);
            
            int[] uv = readIntArray(2*m);
            
            int i;
            
            for (i=0; i<2*m; i++)
            {
                uv[i] --;
                adj_count[uv[i]] ++;
            }
            
            for (i=0; i<N; i++)
            {
                adj_list[i] = new int[adj_count[i]];
                adj_count[i] = 0;
            }
            
            for (i=0; i<m; i++)
            {
                adj_list[uv[2*i]][ adj_count[uv[2*i]]++ ] = uv[2*i+1];
                adj_list[uv[2*i+1]][ adj_count[uv[2*i+1]]++ ] = uv[2*i];
            }
            
            u1 = new int[N];
            u2 = new int[N];
            
            prev = new int[N];
            
            visited = new boolean[N];
            Arrays.fill(visited, false);
            
            int V;
            
            D = new int[N];
            
            dfs(0,-1, 0);
            
            if (max_path >= (N+1)/2)
            {
                int[] path = new int[max_path];
                
                out.println("PATH");
                out.println(max_path);
                
                V = u1[root];
                int k = 0;
                while (V != root)
                {
                    path[k++] = V+1;
                    V = prev[V];
                }
                
                int[] bk = new int[N];
                int bk_size = 0;
                
                path[k++] = root+1;
                
                
                V = u2[root];
                while (V != root)
                {
                    bk[bk_size++] = V;
                    V = prev[V];
                }
                
                for (i=0; i<bk_size; i++)
                {
                    path[k++] = bk[bk_size-i-1]+1;
                }
                
                printArray1(path, max_path);
            }
            else
            {
                
                out.println("PAIRING");
                
                
                boolean[] paired = new boolean[N];
                Arrays.fill(paired, false);
                
                
                int j, k=0, z, U;
                int[]pairs = new int[2*N];
                
                int[] dl = new int[N];
                
                Arrays.fill(dl, 0);
                
                for (i=1; i<N; i++)
                {
                    z = D[i];
                    if (dl[z]>0)
                    {
                        pairs[2*k] = dl[z]+1;
                        pairs[2*k+1] = i+1;
                        dl[z] = 0;
                        k++;
                    }
                    else
                    {
                        dl[z] = i;
                    }
                }
                
                out.println(k);
                
                printArray2(pairs, 2*k);
                        
//                for (i=0; i<k; i++)
//                {
//                   // out.printf("%d %d\n", pairs[i][0]+1, pairs[i][1]+1);
//                }
            }
            
            return null;
            
            //return strf("%f", 0);
            
            //out.printf("Case #%d: \n", caseNumber);
            //return null;
        }
        
        public int caseNumber;
        
        TestCase(int number) {
            caseNumber = number;
        }
        
        public void run(){
            Object r = this.solve();
            
            if ((r != null))
            {
                //outputCaseNumber(r);
                out.println(r);
            }
        }
        
        public String impossible(){
            return "IMPOSSIBLE";
        }
        
        public String strf(String format, Object... args)
        {
            return String.format(format, args);
        }
        
//        public void outputCaseNumber(Object r){
//            //out.printf("Case #%d:", caseNumber);
//            if (r != null)
//            {
//              //  out.print(" ");
//                out.print(r);
//            }
//            out.print("\n");
//        }
    }

    public void run() {
        //while (true)
        {
            int t = multiply_tests ?  readInt() : 1;
            
            if (t==-1)            
            {
                gen_tests();
                return;
            }
            
            for (int i = 0; i < t; i++) {
                TestCase T = new TestCase(i + 1);
                T.run();
            }
        }
    }
    

    
    public Main(BufferedReader _in, PrintStream _out){
        in = _in;
        out = _out;
    }
    

    public static void main(String args[]) {
        Locale.setDefault(Locale.US);
        Main S;
        try {
            S = new Main(
                        new BufferedReader(new InputStreamReader(System.in)),
                        System.out
                );
        } catch (Exception e) {
            return;
        }
        
        S.run();
        
    }

    private StringTokenizer tokenizer = null;

    public int readInt() {
        return Integer.parseInt(readToken());
    }

    public long readLong() {
        return Long.parseLong(readToken());
    }

    public double readDouble() {
        return Double.parseDouble(readToken());
    }

    public String readLn() {
        try {
            String s;
            while ((s = in.readLine()).length() == 0);
            return s;
        } catch (Exception e) {
            return "";
        }
    }

    public String readToken() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(in.readLine());
            }
            return tokenizer.nextToken();
        } catch (Exception e) {
            return "";
        }
    }

    public int[] readIntArray(int n) {
        int[] x = new int[n];
        readIntArray(x, n);
        return x;
    }

    public void readIntArray(int[] x, int n) {
        for (int i = 0; i < n; i++) {
            x[i] = readInt();
        }
    }
    
    public long[] readLongArray(int n) {
        long[] x = new long[n];
        readLongArray(x, n);
        return x;
    }

    public void readLongArray(long[] x, int n) {
        for (int i = 0; i < n; i++) {
            x[i] = readLong();
        }
    }

    public void logWrite(String format, Object... args) {
        if (!log_enabled) {
            return;
        }

        out.printf(format, args);
    }
    
    public void readArrayBuf(int[] x, int n) {
        
        char[]buf = new char[1000000];
        int r = -1;
        int k= 0, l = 0;
        int d;
        
        while (true)
        {
            try{
                l = in.read(buf, 0, 1000000);
            }
            catch(Exception E){};
            
            for (int i=0; i<l; i++)
            {
                if (('0'<=buf[i])&&(buf[i]<='9'))
                {
                    if (r == -1)
                    {
                        r = 0;
                    }
                    d = buf[i] - '0';
                    r = 10 * r + d;
                }
                else
                {
                    if (r != -1)
                    {
                        x[k++] = r;
                    }
                    
                    r = -1;
                }
            }
            
            if (l<1000000)
                return;
        }
    }
    public void printArray1(int[] a, int n)
    {
        int x; 
        int i, l = 0;
        for (i=0; i<n; i++)
        {
            x = a[i];
            
            if (x<0)
            {
                x = -x;
                l++;
            }
            
            if (x==0)
            {
                l++;
            }
            else
            {
                while (x>0)
                {
                    x /= 10;
                    l++;
                }
            }
        }
        
        l += n-1;
        
        char[] s = new char[l];
        
        l--;
        boolean z;
        for (i=n-1; i>=0;  i--)
        {
            x = a[i];
            z = false;            
            if (x<0)
            {
                x = -x;
                z = true;
            }
            
            do{
                s[l--] = (char)('0' + (x % 10));
                x /= 10;
            } while (x>0);
            
            if (z)
            {
                s[l--] = '-';
            }
            
            if (i>0)
            {
                s[l--] = ' ';
            }
        }
        
        out.println(new String(s));
    }
    
    public void printArray2(int[] a, int n)
    {
        int x; 
        int i, l = 0;
        for (i=0; i<n; i++)
        {
            x = a[i];
            
            if (x<0)
            {
                x = -x;
                l++;
            }
            
            if (x==0)
            {
                l++;
            }
            else
            {
                while (x>0)
                {
                    x /= 10;
                    l++;
                }
            }
        }
        
        l += n-1;
        
        char[] s = new char[l];
        
        l--;
        boolean z;
        for (i=n-1; i>=0;  i--)
        {
            x = a[i];
            z = false;            
            if (x<0)
            {
                x = -x;
                z = true;
            }
            
            do{
                s[l--] = (char)('0' + (x % 10));
                x /= 10;
            } while (x>0);
            
            if (z)
            {
                s[l--] = '-';
            }
            
            if (i>0)
            {
                s[l--] = i % 2 == 1 ? ' ' : '\n';
            }
        }
        
        out.println(new String(s));
    }
}