CF1103C Johnny Solving

今天是星期二，这意味着 JOHNNY SOLVING 团队又有争论了：他们试图搞清楚谁是 Johnny，谁是 Solving。因此，他们请 Umnik 来帮忙。Umnik 给了他们一个连通图，这个图有 $n$ 个顶点，没有自环和重边，且每个顶点的度数至少为 $3$，同时还给了一个数 $1 \leq k \leq n$。由于 Johnny 不太聪明，他承诺能在图中找到一条长度至少为 $\frac{n}{k}$ 的简单路径。作为回应，Solving 承诺能找到 $k$ 个互不相交的简单顶点环，并且每个环都满足： - 每个环的长度至少为 $3$。 - 每个环的长度不能被 $3$ 整除。 - 每个环中必须有一个“代表”顶点，这个顶点在所有输出的环中只属于这一环。 你需要帮助他们解决争论，也就是说，你需要为 Johnny 找到一条长度至少为 $\frac{n}{k}$ 的简单路径，或者为 Solving 找到 $k$ 个满足上述条件的环。如果没有任何一种方案，输出 $-1$。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq k \leq n \leq 2.5 \times 10^5, 1 \leq m \leq 5 \times 10^5$）。 接下来的 $m$ 行描述图中的边，每行包含两个整数 $v$ 和 $u$（$1 \leq v, u \leq n$）。保证 $v \neq u$，且所有 $m$ 对都是不同的。 保证每个顶点的度数至少为 $3$。

如果你为 Johnny 找到了解决方案，第一行输出 `PATH`。第二行输出路径上的顶点数 $c$（$c \geq \frac{n}{k}$）。第三行按顺序输出路径上的顶点编号。 如果你为 Solving 找到了解决方案，第一行输出 `CYCLES`。接下来的 $k$ 行，每两行描述一个环：第一行输出环的大小 $c$（$c \geq 3$），第二行按顺序输出环上的顶点编号。环的第一个顶点必须是该环的代表。 如果没有任何方案，输出 $-1$。输出中的所有数字总数不得超过 $10^6$。保证如果存在解，则一定存在满足该限制的正确输出。

由 ChatGPT 4.1 翻译