CF263D Cycle in Graph

给定一个无向图 $G$，由 $n$ 个节点组成。图中的节点编号为 $1$ 到 $n$。已知图 $G$ 的每个节点都与至少 $k$ 个其它节点通过边相连。你的任务是在给定的图中找出一个长度至少为 $k+1$ 的简单环。 在图 $G$ 中，长度为 $d$（$d>1$）的简单环是由 $d$ 个互不相同的图节点 $v_{1}, v_{2}, \ldots, v_{d}$ 构成的序列，使得节点 $v_{1}$ 和 $v_{d}$ 之间有一条图中的边，并且对于任意的整数 $i$，$1 \leq i < d$，节点 $v_{i}$ 和 $v_{i+1}$ 之间也有一条图中的边。

第一行包含三个整数 $n$、$m$、$k$（$3 \leq n, m \leq 10^{5}$，$2 \leq k \leq n-1$）——表示图的节点数、边数和每个节点的度数下界。接下来的 $m$ 行，每行包含两个整数 $a_{i}$、$b_{i}$（$1 \leq a_{i}, b_{i} \leq n$，$a_{i} \ne b_{i}$），表示第 $i$ 条边连接的节点编号。 保证给定的图中没有重边和自环，并且每个节点都与至少 $k$ 个其它节点通过边相连。

第一行输出一个整数 $r$（$r \geq k+1$），表示找到的环的长度。第二行输出 $r$ 个两两不同的整数 $v_{1}, v_{2}, \ldots, v_{r}$（$1 \leq v_{i} \leq n$），表示该简单环中节点的编号。 保证一定存在满足条件的答案。如果有多组符合条件的答案，可以输出任意一组。

由 ChatGPT 5 翻译