邪恶的 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 个顶点的约束。