题目链接

题意

已知一个图，你需要完成下面两个任务中的一个。

• 找到一条长度大于等于 $\lceil \frac{n}{2} \rceil$ 的链。

• 选出若干个点对，使得至少包括 $\lceil \frac{n}{2} \rceil$ 个点，且不能包含相同的点，且对于任意两个点对 $(a,b),(c,d)$，需要满足 ${a,b,c,d}$ 的子图中的边小于等于 $2$。

输入格式

第一行一个数 $t$，数据组数。

下面每组数据两个数 $n,m$，表示点和边。

下面 $m$ 行，输入一条边。

输出格式

对于每组数据，如果满足第一个条件，输出 PATH。

然后下面输出一条链。

否则输出 PAIRING。

然后下面输出点对。

样例

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

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