{"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 公司在庞大的地下实验室中为残酷的实验克隆生物。有一次，该公司克隆了一个名叫 Andryusha 的男孩，他比他的同伴更聪明。Andryusha 立刻意识到那里正在进行某些可疑的活动。他团结其他克隆体反抗邪恶公司，并开始寻找实验室的出口。公司不得不决定摧毁整个实验室。\n\n实验室可以被看作一个包含 #cf_span[n] 个顶点和 #cf_span[m] 条边的连通图。#cf_span[k] 个 Andryusha 的克隆体从某些顶点出发寻找出口。每个克隆体每秒可以遍历一条边。任意数量的克隆体可以同时位于同一顶点。每个克隆体可以在任意时刻停止搜索，但必须至少访问其起始顶点一次。出口可能位于实验室的任意顶点，因此每个顶点都必须被至少一个克隆体访问。\n\n每个克隆体在实验室爆炸前最多能访问 #cf_span[\\left\\lceil \\frac{n}{k} \\right\\rceil] 个顶点。\n\n你的任务是为克隆体选择起始顶点和搜索路径。每条路径最多包含 #cf_span[\\left\\lceil \\frac{n}{k} \\right\\rceil] 个顶点。\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]）—— 表示第 #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]）—— 表示第 #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 $ clones.  \nLet $ d_{\\max} $ be the maximum number of vertices each clone may visit (implicitly given by problem context; note: sample constraints imply $ d_{\\max} = 6 $ and $ d_{\\max} = 5 $, but exact value must be inferred from context — **problem statement is incomplete** as $ d_{\\max} $ is not numerically specified).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ n - 1 \\leq m \\leq 2 \\cdot 10^5 $  \n3. $ 1 \\leq k \\leq n $  \n4. Graph $ G $ is connected (may have self-loops and multiple edges).  \n5. Each clone must:  \n   - Start at a vertex in $ V $.  \n   - Visit at most $ d_{\\max} $ vertices (including start).  \n   - Visit its starting vertex at least once.  \n6. Every vertex in $ V $ must be visited by at least one clone.  \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}) $ satisfies:  \n- $ c_i \\leq d_{\\max} $,  \n- $ v_{i,1} $ is the starting vertex of clone $ i $,  \n- $ \\{v_{i,j} \\mid 1 \\leq j \\leq c_i, 1 \\leq i \\leq k\\} = V $,  \n- For each $ j \\in \\{2, \\dots, c_i\\} $, $ \\{v_{i,j-1}, v_{i,j}\\} \\in E $ (adjacent or same via self-loop).  \n\nOutput: $ k $ sequences $ W_1, \\dots, W_k $.  \n\n*(Note: $ d_{\\max} $ is not explicitly given in input — likely a typo/omission. Based on samples, assume $ d_{\\max} = \\lceil n/k \\rceil + \\text{buffer} $, but formal problem requires this value to be specified.)*","simple_statement":null,"has_page_source":false}