← 返回题目列表

Codeforces · 780/E

E. 地下实验室

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

邪恶的 Bumbershoot 公司在一个巨大的地下实验室中生产用于可怕实验的克隆人。有一次,该公司克隆了一个比他的战友更聪明的男孩安德留沙。安德留莎立刻意识到那里有什么可疑的事情发生。他召集了克隆人同伴,与邪恶公司展开了斗争,他们开始寻找实验室的出口。该公司不得不减少对实验室综合体的破坏。

实验室可以被描绘为具有 n 个顶点和 m 个边的连通图。 Andryusha 的 k 个克隆体开始在某些顶点寻找出口。每个克隆每秒可以遍历任何边缘一次。允许任意数量的克隆同时位于任意顶点。每个分身都可以在任何时刻停止注视,但他至少必须注视自己的起始顶点。出口可以位于实验室的任何顶点,因此每个顶点必须至少有一个克隆体访问过。

在实验室爆炸之前,每个克隆最多可以访问 $$\left\lceil \frac{2n}{k} \right\rceil$$ 个顶点。

你的任务是选择克隆的起始顶点并搜索路径。每条路线最多可以有 $$\left\lceil \frac{2n}{k} \right\rceil$$ 个顶点。

输入

第一行包含三个整数 n、m 和 k (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105, 1 ≤ k ≤ n) - 实验室中的顶点和边的数量以及克隆的数量。

接下来的 m 行中的每一行都包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ n) - 由相应边连接的顶点索引。图允许有自环和多边。

该图保证是连通的。

输出

你应该打印 k 行。其中第 i 行必须以整数 ci 开头 ($$1 \leq c_i \leq \left\lceil \frac{2n}{k} \right\rceil$$) — 第 i 个克隆访问的顶点数,后跟 ci 整数 — 此克隆按访问顺序访问的顶点索引。每次访问每个顶点时,无论是否之前访问过它,都必须打印它。

保证存在有效答案。

示例

输入 #1

3 2 1
2 1
3 1

输出 #1

3 2 1 3

输入 #2

5 4 2
1 2
1 3
1 4
1 5

输出 #2

3 2 1 3
3 4 1 5

注意

在第一个示例案例中,只有一个克隆可以按顺序 (2, 1, 3) 访问顶点,这符合每个克隆 6 个顶点的约束。

在第二个示例案例中,两个克隆可以按 (2, 1, 3) 和 (4, 1, 5) 的顺序访问顶点,这符合每个克隆 5 个顶点的约束。