CF263D.Cycle in Graph

You've got a undirected graph G, consisting of n nodes. We will consider the nodes of the graph indexed by integers from 1 to n. We know that each node of graph G is connected by edges with at least k other nodes of this graph. Your task is to find in the given graph a simple cycle of length of at least k + 1.

A simple cycle of length d (d > 1) in graph G is a sequence of distinct graph nodes _v_1, _v_2, ..., v__d such, that nodes _v_1 and v__d are connected by an edge of the graph, also for any integer i (1 ≤ i < d) nodes v__i and v__i + 1 are connected by an edge of the graph.

你有一个包含 $n$ 个节点的无向图 $G$。我们将图中的节点用从 $1$ 到 $n$ 的整数进行编号。已知图 $G$ 中每个节点至少与该图中其余 $k$ 个节点通过边相连。你的任务是在给定图中找出一个长度至少为 $k+1$ 的简单环。

图 $G$ 中长度为 $d$（$d > 1$）的简单环，是指一串互不相同的图节点 $v_1,\,v_2,\,\dots,\,v_d$，满足：节点 $v_1$ 与 $v_d$ 之间存在图的一条边；且对任意整数 $i$（$1 \le i < d$），节点 $v_i$ 与 $v_{i+1}$ 之间也存在图的一条边。

The first line contains three integers n, m, k (3 ≤ n, m ≤ 105; 2 ≤ k ≤ n - 1) — the number of the nodes of the graph, the number of the graph's edges and the lower limit on the degree of the graph node. Next m lines contain pairs of integers. The i-th line contains integers a__i, b__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i) — the indexes of the graph nodes that are connected by the i-th edge.

It is guaranteed that the given graph doesn't contain any multiple edges or self-loops. It is guaranteed that each node of the graph is connected by the edges with at least k other nodes of the graph.

第一行包含三个整数 $n$、$m$、$k$（$3 \leq n, m \leq 10^5$；$2 \leq k \leq n - 1$）—— 分别表示图的节点数、边数以及图中节点度数的下限。接下来的 $m$ 行每行包含一对整数。第 $i$ 行包含整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$；$a_i \neq b_i$）—— 表示由第 $i$ 条边所连接的两个图节点的编号。

保证给定图中不包含重边或自环。同时保证图中每个节点至少与图中其余 $k$ 个节点通过边相连。

In the first line print integer r (r ≥ k + 1) — the length of the found cycle. In the next line print r distinct integers _v_1, _v_2, ..., v__r (1 ≤ v__i ≤ n) — the found simple cycle.

It is guaranteed that the answer exists. If there are multiple correct answers, you are allowed to print any of them.

第一行输出整数 $r$（$r \geq k + 1$）—— 找到的环的长度。
第二行输出 $r$ 个互不相同的整数 $v_1,\,v_2,\,\dots,\,v_r$（$1 \leq v_i \leq n$）—— 找到的简单环。

保证答案存在。若存在多个正确答案，输出任意一个即可。