{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\nEach clone can visit at most vertices before the lab explodes.\n\nYour task is to choose starting vertices and searching routes for the clones. Each route can have at most vertices."},{"iden":"input","content":"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.\n\nEach 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.\n\nThe graph is guaranteed to be connected."},{"iden":"output","content":"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.\n\nIt is guaranteed that a valid answer exists."},{"iden":"examples","content":"Input\n\n3 2 1\n2 1\n3 1\n\nOutput\n\n3 2 1 3\n\nInput\n\n5 4 2\n1 2\n1 3\n1 4\n1 5\n\nOutput\n\n3 2 1 3\n3 4 1 5"},{"iden":"note","content":"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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"邪恶的 Bumbershoot 公司在庞大的地下实验室中为残酷的实验克隆生物。有一次，该公司克隆了一个名叫安德留沙的男孩，他比其他克隆体更聪明。安德留沙立刻意识到那里正在发生某些可疑的事情。他团结其他克隆体反抗邪恶公司，并开始寻找实验室的出口。公司不得不决定摧毁整个实验室复合体。\n\n实验室可以被看作一个具有 #cf_span[n] 个顶点和 #cf_span[m] 条边的连通图。#cf_span[k] 个安德留沙的克隆体从某些顶点出发寻找出口。每个克隆体每秒可以遍历一条边。任意数量的克隆体可以同时位于同一个顶点。每个克隆体可以在任意时刻停止搜索，但他必须至少访问自己的起始顶点一次。出口可能位于实验室的任意顶点上，因此每个顶点都必须被至少一个克隆体访问。\n\n每个克隆体在实验室爆炸前最多能访问 #cf_span[\\left\\lceil \\frac{n}{k} \\right\\rceil + 2] 个顶点。\n\n你的任务是为克隆体选择起始顶点和搜索路径。每条路径最多包含 #cf_span[\\left\\lceil \\frac{n}{k} \\right\\rceil + 2] 个顶点。\n\n第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 2·10^5], #cf_span[n - 1 ≤ m ≤ 2·10^5], #cf_span[1 ≤ k ≤ n]）——分别表示实验室的顶点数、边数和克隆体数量。\n\n接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ n]）——表示由该边连接的两个顶点的编号。图允许存在自环和多重边。\n\n保证图是连通的。\n\n你需要输出 #cf_span[k] 行。第 #cf_span[i] 行必须以一个整数 #cf_span[ci] 开头（#cf_span[1 ≤ ci ≤ \\left\\lceil \\frac{n}{k} \\right\\rceil + 2]）——表示第 #cf_span[i] 个克隆体访问的顶点数，随后是 #cf_span[ci] 个整数——表示该克隆体按访问顺序经过的顶点编号。你必须每次访问顶点时都输出它，无论之前是否已访问过。\n\n保证存在合法答案。\n\n在第一个样例中，只有一个克隆体，可以按顺序访问顶点 (2, 1, 3)，符合每个克隆体最多访问 6 个顶点的限制。\n\n在第二个样例中，两个克隆体可以分别按顺序访问顶点 (2, 1, 3) 和 (4, 1, 5)，符合每个克隆体最多访问 5 个顶点的限制。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 2·10^5], #cf_span[n - 1 ≤ m ≤ 2·10^5], #cf_span[1 ≤ k ≤ n]）——分别表示实验室的顶点数、边数和克隆体数量。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ n]）——表示由该边连接的两个顶点的编号。图允许存在自环和多重边。保证图是连通的。"},{"iden":"output","content":"你应该输出 #cf_span[k] 行。第 #cf_span[i] 行必须以一个整数 #cf_span[ci] 开头（#cf_span[1 ≤ ci ≤ \\left\\lceil \\frac{n}{k} \\right\\rceil + 2]）——表示第 #cf_span[i] 个克隆体访问的顶点数，随后是 #cf_span[ci] 个整数——表示该克隆体按访问顺序经过的顶点编号。你必须每次访问顶点时都输出它，无论之前是否已访问过。保证存在合法答案。"},{"iden":"examples","content":"输入\n3 2 1\n2 1\n3 1\n输出\n3 2 1 3\n\n输入\n5 4 2\n1 2\n1 3\n1 4\n1 5\n输出\n3 2 1 3\n3 4 1 5"},{"iden":"note","content":"在第一个样例中，只有一个克隆体，可以按顺序访问顶点 (2, 1, 3)，符合每个克隆体最多访问 6 个顶点的限制。在第二个样例中，两个克隆体可以分别按顺序访问顶点 (2, 1, 3) 和 (4, 1, 5)，符合每个克隆体最多访问 5 个顶点的限制。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ |V| = n $, $ |E| = m $, and $ k \\in \\mathbb{Z}^+ $ clones.  \nLet $ L \\in \\mathbb{Z}^+ $ be the maximum number of vertices each clone may visit (implicitly given by context: $ L = \\lceil n/k \\rceil + \\text{some bound} $, but problem states \"each clone can visit at most [missing] vertices\"; from samples, infer $ L $ is such that total capacity $ k \\cdot L \\geq n $, and solution exists).\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $, $ n-1 \\leq m \\leq 2 \\cdot 10^5 $, $ 1 \\leq k \\leq n $  \n2. $ G $ is connected (may have self-loops and multiple edges)  \n3. Each clone starts at some vertex and traverses a walk (sequence of vertices where consecutive vertices are adjacent or same)  \n4. Each clone’s walk has length at most $ L $ (i.e., at most $ L $ vertices visited, counting repetitions)  \n5. Every vertex in $ V $ must appear in at least one clone’s walk  \n6. Each clone must visit its starting vertex at least once (trivially satisfied if walk starts there)  \n7. It is guaranteed that a valid assignment exists  \n\n**Objective**  \nFind $ k $ walks $ W_1, W_2, \\dots, W_k $, where each $ W_i = (v_{i,1}, v_{i,2}, \\dots, v_{i,c_i}) $, $ c_i \\leq L $, such that:  \n- $ v_{i,1} $ is the starting vertex of clone $ i $  \n- $ \\{v_{i,j} \\mid 1 \\leq i \\leq k, 1 \\leq j \\leq c_i\\} = V $  \n- For each $ i $ and $ j \\in \\{2, \\dots, c_i\\} $, $ \\{v_{i,j-1}, v_{i,j}\\} \\in E $ or $ v_{i,j-1} = v_{i,j} $ (i.e., walk respects edge connectivity or stays put)  \n- Output each walk as a sequence of visited vertices (with repetitions)","simple_statement":null,"has_page_source":false}