← 返回题目列表

Codeforces · 263/D

D. 图表中的循环

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

你有一个无向图 G,由 n 个节点组成。我们将考虑由 1 到 n 的整数索引的图的节点。我们知道图 G 的每个节点都通过边与该图的至少 k 个其他节点连接。你的任务是在给定的图中找到一个长度至少为 k + 1 的简单循环。

图 G 中长度为 d (d > 1) 的简单循环是一系列不同的图节点 v1, v2, ..., vd,使得节点 v1 和 vd 通过图的边连接,同样对于任何整数 i (1 ≤ i < d),节点 vi 和 vi + 1 通过图的边连接。

输入

第一行包含三个整数 n、m、k (3 ≤ n, m ≤ 105; 2 ≤ k ≤ n - 1) — 图的节点数、图的边数以及图节点度的下限。接下来的 m 行包含整数对。第 i 行包含整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 由第 i 条边连接的图节点的索引。

保证给定的图不包含任何重边或自循环。保证图的每个节点都通过边与图的至少 k 个其他节点连接。

输出

在第一行打印整数 r (r ≥ k + 1) — 找到的循环的长度。在下一行中打印 r 个不同的整数 v1, v2, ..., vr (1 ≤ vi ≤ n) — 找到的简单循环。

保证答案存在。如果有多个正确答案,您可以打印其中任何一个。

示例

输入 #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