← 返回题目列表

Codeforces · 1103/C

C. 约翰尼解决

中文机器翻译题面 查看原题

今天是星期二,这意味着 JOHNNY SOLVING 团队再次出现争议:他们试图了解谁是 Johnny,谁是 Solving。这就是为什么人们要求乌姆尼克帮助他们。 Umnik 给了大家一个有 $$$n$$$ 个顶点的连通图,没有循环和多重边,这样任何顶点的度数至少为 $$$3$$$,并且他还给出了一个数字 $$$1 \leq k \leq n$$$。因为约翰尼不太聪明,他答应在图中找到一条长度至少为 $$$\frac{n}{k}$$$ 的简单路径。作为答复,Solving 承诺通过具有代表的顶点循环来找到 $$$k$$$ 简单,这样:

- 每个周期的长度至少为 $$$3$$$。
- 每个周期的长度不能被 $$$3$$$ 整除。
- 每个循环中必须有一个代表 - 顶点,该顶点在所有打印循环中仅属于该循环。

你需要帮助大家解决争端,因为你需要为Johnny找到一个解决方案:一条长度至少为$$$\frac{n}{k}$$$的简单路径($$$n$$$不一定除以$$$k$$$),或者解决方案:满足上述所有条件的$$$k$$$循环。如果没有任何解决方案 - 打印$$$-1$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 2.5 \cdot 10^5, 1 \leq m \leq 5 \cdot 10^5$$$)

接下来的 $$$m$$$ 行以 $$$v$$$, $$$u$$$ ($$$1 \leq v, u \leq n$$$) 的格式描述图形的边缘。保证 $$$v \neq u$$$ 和所有 $$$m$$$ 对是不同的。

保证每个顶点的度数至少为$$$3$$$。

输出

如果你为 Johnny 解决了问题,请在第一行打印 PATH。在第二行中打印路径 $$$c$$$ ($$$c \geq \frac{n}{k}$$$) 中的顶点数。在第三行中打印描述路径顺序的顶点。

如果您解决了解决问题,则在第一行打印 CYCLES。在下面的行中,按以下格式准确描述 $$$k$$$ 周期:在第一行中打印周期 $$$c$$$ 的大小 ($$$c \geq 3$$$)。在第二行中按路线顺序打印循环。此外,循环中的第一个顶点必须是代表。

如果没有任何解决方案,则打印$$$-1$$$。输出中打印的数字总数不得超过 $$$10^6$$$。可以保证,如果存在任何解决方案,则有一个正确的输出满足此限制。

示例

输入 #1

4 6 2
1 2
1 3
1 4
2 3
2 4
3 4

输出 #1

PATH
4
1 2 3 4

输入 #2

10 18 2
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
3 4
2 4
5 6
6 7
5 7
8 9
9 10
8 10

输出 #2

CYCLES
4
4 1 2 3 
4
7 1 5 6