CF1391E.Pairs of Pairs

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 $\lceil \frac{n}{2} \rceil$ nodes. Here, a path is called simple if it does not visit any node multiple times.
• Find a valid pairing in which at least $\lceil \frac{n}{2} \rceil$ 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.

你有一个由 $n$ 个节点和 $m$ 条边组成的简单且连通的无向图。

考虑任意一种方式，从这 $n$ 个节点中选取某个子集，并将其中节点两两配对，使得每个节点至多出现在一个配对中。

若对任意两个配对 $(a,b)$ 和 $(c,d)$，由节点集合 $\{a,b,c,d\}$ 所诱导的子图中至多包含 $2$ 条边（共 $6$ 种可能的边），则该配对称为合法的。更严格地说，对于任意两个配对 $(a,b)$ 和 $(c,d)$，由节点 $\{a,b,c,d\}$ 诱导的子图应至多含 $2$ 条边。

请注意：一个节点集合所诱导的子图仅包含该集合中的节点，以及两个端点均属于该集合的所有边。

现在，请完成以下二者之一：

• 找出一条至少包含 $\lceil \frac{n}{2} \rceil$ 个节点的简单路径（即不重复经过任一节点的路径）；
• 找出一个合法的配对，其中至少有 $\lceil \frac{n}{2} \rceil$ 个节点被配对。

可以证明：对于满足题目约束条件的任意图，上述两种方案中至少有一种总能实现。

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

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

The next $m$ lines each contain $2$ integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq 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\cdot 10^5$.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$2 \le n \le 5\cdot 10^5$，$1 \le m \le 10^6$），分别表示图中节点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示图中节点 $u$ 与节点 $v$ 之间存在一条无向边。

保证所给图是连通的，且是简单图——即任意一对节点间至多只有一条边，且不存在自环。

保证所有测试用例的 $n$ 之和不超过 $5\cdot 10^5$。

保证所有测试用例的 $m$ 之和不超过 $10^6$。

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$ ($\lceil \frac{n}{2} \rceil \le 2\cdot k \le 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$ ($\lceil \frac{n}{2} \rceil \le k \le n$), the number of nodes in your path.
• Then, in the second line, output $k$ integers, $v_1, v_2, \ldots, 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 \le i \lt k$).
• This path has to be simple, meaning no node should appear more than once.

对于每个测试用例，输出格式如下：

若你找到了一个配对方案，则在第一行输出 "PAIRING"（不带引号）。

• 接着，输出 $k$（满足 $\lceil \frac{n}{2} \rceil \le 2\cdot k \le n$），表示你所构造的配对方案中包含的配对数量；
• 然后，在接下来的 $k$ 行中，每行输出两个整数 $a$ 和 $b$，表示 $a$ 与 $b$ 相互配对。注意：图中 不一定 存在连接 $a$ 和 $b$ 的边！
• 该配对方案必须合法，且每个节点至多属于一个配对。

否则（即未找到配对方案），在第一行输出 "PATH"（不带引号）。

• 接着，输出 $k$（满足 $\lceil \frac{n}{2} \rceil \le k \le n$），表示你所构造的路径中包含的节点数量；
• 然后，在第二行输出 $k$ 个整数 $v_1, v_2, \ldots, v_k$，按它们在路径中出现的顺序排列。形式化地，对每个 $i$（$1 \le i \lt k$），$v_i$ 与 $v_{i+1}$ 之间必须存在一条边；
• 该路径必须是简单路径，即任意节点至多出现一次。

The path outputted in the first case is the following.

The pairing outputted in the second case is the following.

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

Here is the pairing outputted in the third case.

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.

第一种情况输出的路径如下所示。

第二种情况输出的配对如下所示。

以下是同一图的一个无效配对——子图 ${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)$。

第四种情况输出的配对如下所示。