你有一个无向图 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