Cycle in Graph

题意翻译

给定一个$n$个节点组成的无向图$G$, 图$G$的每个节点与至少$k$个其他节点相连。请找出找到一个长度至少为$k+1$的**简单环**。 **简单环**的定义:图$G$中长度为$d(d> 1)$的简单循环是一系列不同的图节点 $v_1,v_2,\cdots ,v_d$ ,使得节点$v_1$和$v_d$右边相连. 对于任何整数$i(1\leq i < d)$个节点$v_i$和$v_i + 1$通过图的边缘连接。

题目描述

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&gt;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&lt;d) $ nodes $ v_{i} $ and $ v_{i+1} $ are connected by an edge of the graph.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , $ k $ $ (3<=n,m<=10^{5}; 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.

输出格式

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.

输入输出样例

输入样例 #1

3 3 2
1 2
2 3
3 1

输出样例 #1

3
1 2 3 

输入样例 #2

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

输出样例 #2

4
3 4 1 2