CF780E.Underground Lab

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.

邪恶的“雨伞”公司在一个庞大的地下实验室中制造克隆体，用于残忍的实验。有一次，该公司克隆了一个名叫安德留沙的男孩，他比其他克隆体更为聪明。安德留沙立刻意识到那里正发生着某种可疑的事情。他号召其他克隆体联合起来，与这家邪恶公司展开斗争，并出发寻找实验室的出口。该公司被迫采取措施摧毁整个实验室设施。

该实验室可建模为一个包含 $n$ 个顶点和 $m$ 条边的连通图。$k$ 个安德留沙的克隆体从图中某些顶点出发，开始搜寻出口。每个克隆体每秒可遍历任意一条边一次。任意数量的克隆体可同时位于同一顶点。每个克隆体可在任意时刻停止搜索，但必须至少访问其起始顶点一次。出口可能位于实验室的任意一个顶点，因此每个顶点都必须被至少一个克隆体访问到。

在实验室爆炸前，每个克隆体最多能访问 个顶点。

你的任务是为这些克隆体选定起始顶点及搜索路径。每条路径至多包含 个顶点。

The first line contains three integers n, m, and k (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105, 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.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n ≤ 2·10^5$，$n - 1 ≤ m ≤ 2·10^5$，$1 ≤ k ≤ n$）—— 分别表示实验室中的顶点数、边数以及克隆体数量。

接下来的 $m$ 行中，每行包含两个整数 $x_i$ 和 $y_i$（$1 ≤ x_i,\,y_i ≤ n$）—— 表示由对应边所连接的两个顶点的编号。该图允许存在自环和重边。

保证该图是连通的。

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.

你需要输出 k 行。其中第 i 行必须以一个整数 c__i（）开头，表示第 i 个克隆所访问的顶点数量；随后是 c__i 个整数，表示该克隆按访问顺序所经过的顶点编号。每次访问某个顶点时，都必须将其输出，无论该顶点此前是否已被访问过。

保证存在合法解。

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.

在第一个样例中，仅有一个克隆体，其可按顺序访问顶点 (2, 1, 3)，满足每个克隆体最多访问 6 个顶点的约束。

在第二个样例中，两个克隆体可分别按顺序访问顶点 (2, 1, 3) 和 (4, 1, 5)，满足每个克隆体最多访问 5 个顶点的约束。