您有一个简单且连通的无向图,由 $$$n$$$ 节点和 $$$m$$$ 边组成。
考虑以任何方式对这些 $$$n$$$ 节点的某些子集进行配对,以便没有节点出现在多于一对中。
如果对于每对对,包含所有 $$$4$$$ 节点(每对两个)的导出子图最多具有 $$$2$$$ 边(在 $$$6$$$ 可能的边中),则此配对有效。更正式地说,对于任意两对 $$$(a,b)$$$ 和 $$$(c,d)$$$,具有节点 $$$\{a,b,c,d\}$$$ 的导出子图最多应具有 $$$2$$$ 边。
请注意,由一组节点导出的子图仅包含来自该组的节点以及其两个端点都在该组中的边。
现在,执行以下操作之一:
- 找到一条至少由 $$$\lceil \frac{n}{2} \rceil$$$ 节点组成的简单路径。这里,如果一条路径没有多次访问任何节点,则该路径被称为简单路径。
- 查找至少 $$$\lceil \frac{n}{2} \rceil$$$ 节点配对的有效配对。
可以证明,可以在每个图中找到满足语句约束的至少两者之一。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含 $$$2$$$ 整数 $$$n, m$$$ ($$$2 \le n \le 5\cdot 10^5$$$, $$$1 \le m \le 10^6$$$),分别表示节点和边的数量。
接下来的 $$$m$$$ 行每行包含 $$$2$$$ 整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),表示给定图中节点 $$$u$$$ 和 $$$v$$$ 之间存在无向边。
保证给定的图是连通的,并且简单——它不包含同一对节点之间的多条边,也不具有任何自环。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。
保证所有测试用例的$$$m$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出格式如下。
如果您找到了配对,请在第一行输出“PAIRING”(不带引号)。
- 然后,输出 $$$k$$$ ($$$\lceil \frac{n}{2} \rceil \le 2\cdot k \le n$$$),即配对中的对数。
- 然后,在接下来的 $$$k$$$ 行中,输出 $$$2$$$ 整数 $$$a$$$ 和 $$$b$$$ — 表示 $$$a$$$ 和 $$$b$$$ 彼此配对。请注意,图形不必在 $$$a$$$ 和 $$$b$$$ 之间有边!
- 该配对必须有效,并且每个节点必须是最多 $$$1$$$ 对的一部分。
否则,在第一行输出“PATH”(不带引号)。
- 然后,输出 $$$k$$$ ($$$\lceil \frac{n}{2} \rceil \le k \le n$$$),即路径中的节点数。
- 然后,在第二行中,按照它们出现在路径上的顺序输出 $$$k$$$ 整数,$$$v_1, v_2, \ldots, v_k$$$。形式上,对于每个 $$$i$$$,$$$v_i$$$ 和 $$$v_{i+1}$$$ 之间应该有一条边($$$1 \le i < k$$$)。
- 该路径必须简单,这意味着任何节点都不应出现多次。
示例
输入 #1
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
输出 #1
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
注意
第一种情况输出的路径如下。
第二种情况下输出的配对如下。
这是同一图的无效配对 - 子图 $$$\{1,3,4,5\}$$$ 具有 $$$3$$$ 边。
这是第三种情况下输出的配对。
这是有效的,因为——
- 子图 $$$\{1,8,2,5\}$$$ 具有边 ($$$1$$$,$$$2$$$) 和 ($$$1$$$,$$$5$$$)。
- 子图 $$$\{1,8,4,10\}$$$ 具有边 ($$$1$$$,$$$4$$$) 和 ($$$4$$$,$$$10$$$)。
- 子图 $$$\{4,10,2,5\}$$$ 具有边 ($$$2$$$,$$$4$$$) 和 ($$$4$$$,$$$10$$$)。
这是第四种情况下输出的配对。