Underground Lab

题意翻译

## 题目描述 邪恶的 Bumbershoot 公司在一个巨大的地下实验室里制造克隆人来进行可怕的实验。有一次，该公司克隆了一个比他的同伴更聪明的男孩安德里沙。安德里沙很快意识到，这个实验室发生了一些蹊跷的事情。他召集了克隆人同伴们去与邪恶的守卫兵团斗争。于是他们开始寻找实验室的出口。守护兵团不得不摧毁实验室的建筑群。 实验室可以看作是一个有 $n$ 个顶点和 $m$ 条边的无向图，$k$ 个安德里沙的克隆人同伴开始在一些顶点中寻找出口。每个克隆人每秒可以在任何顶点之间穿越一次，并且允许在任意一个顶点存在任何数量的克隆人。这些克隆人可以在任何时候停止寻找，但他在他的起始顶点必须寻找。出口可以位于实验室的任何一顶点，因此每个顶点必须至少有一个克隆人访问。 在实验室爆炸之前，每个克隆人最多只能访问 $\left\lceil\dfrac{2n}{k}\right\rceil$ 个顶点。 你的任务是选择起始顶点和克隆人的搜索路线。 每条路线可以有最多 $\left\lceil\dfrac{2n}{k}\right\rceil$ 个顶点。 ## 输入格式 第一行包含三个整数 $n$、$m$ 和 $k\ (1\leq n \leq 2\times 10^{5}, n-1\leq m \leq 2\times 10^{5}, 1\leq k \leq n)$。它们分别为实验室中的顶点和边的数量，以及克隆人的数量。 接下来的 $m$ 行中，每行都包含两个整数 $x_{i}$ 和 $y_{i} (1\leq x_{i},y_{i}\leq n)$，为各自边连接的顶点的编号。 该图可能会有重边和负环。 保证图是联通的。 ## 输出格式 输出 $k$ 行。 其中第 $i$ 行必须以一个整数 $c_{i} (1\leq c_{i} \leq \left\lceil\dfrac{2n}{k}\right\rceil)$ 开始，此为第 $i$ 个克隆人所访问过的顶点数量，在 $c_{i}$ 后面跟着这个克隆人所访问的顶点的编号，按访问顺序排列。每次访问任一顶点时都要输出，即使它在之前被访问过。 保证存在一个有效的答案。

题目描述

The evil Bumbershoot corporation produces clones for gruesome experiments in a vast underground lab. On one occasion, the corp cloned a boy Andryusha who was smarter than his comrades. Immediately Andryusha understood that something fishy was going on there. He rallied fellow clones to go on a feud against the evil corp, and they set out to find an exit from the lab. The corp had to reduce to destroy the lab complex. The lab can be pictured as a connected graph with $ n $ vertices and $ m $ edges. $ k $ clones of Andryusha start looking for an exit in some of the vertices. Each clone can traverse any edge once per second. Any number of clones are allowed to be at any vertex simultaneously. Each clone is allowed to stop looking at any time moment, but he must look at his starting vertex at least. The exit can be located at any vertex of the lab, hence each vertex must be visited by at least one clone. Each clone can visit at most  vertices before the lab explodes. Your task is to choose starting vertices and searching routes for the clones. Each route can have at most  vertices.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , and $ k $ ( $ 1<=n<=2·10^{5} $ , $ n-1<=m<=2·10^{5} $ , $ 1<=k<=n $ ) — the number of vertices and edges in the lab, and the number of clones. Each of the next $ m $ lines contains two integers $ x_{i} $ and $ y_{i} $ ( $ 1<=x_{i},y_{i}<=n $ ) — indices of vertices connected by the respective edge. The graph is allowed to have self-loops and multiple edges. The graph is guaranteed to be connected.

输出格式

You should print $ k $ lines. $ i $ -th of these lines must start with an integer $ c_{i} $ () — the number of vertices visited by $ i $ -th clone, followed by $ c_{i} $ integers — indices of vertices visited by this clone in the order of visiting. You have to print each vertex every time it is visited, regardless if it was visited earlier or not. It is guaranteed that a valid answer exists.

输入输出样例

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

说明

In the first sample case there is only one clone who may visit vertices in order (2, 1, 3), which fits the constraint of 6 vertices per clone. In the second sample case the two clones can visited vertices in order (2, 1, 3) and (4, 1, 5), which fits the constraint of 5 vertices per clone.