Codeforces Round #403 E. Underground Lab（思维+搜索）

E. Underground Lab

Description

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 ⌈2nk⌉$/lceil /frac{2n}{k} /rceil$ vertices before the lab explodes.

Your task is to choose starting vertices and searching routes for the clones. Each route can have at most ⌈2nk⌉$/lceil /frac{2n}{k} /rceil$ vertices.

Input

The first line contains three integers n, m, and k (1≤n≤2⋅105,n−1≤m≤2⋅105,1≤k≤n)$(1/le n/le2/cdot10^5, n-1/le m/le2/cdot10^5,1/le k /le n)$— the number of vertices and edges in the lab, and the number of clones.

Each of the next m lines contains two integers xi$x_i$ and yi$y_i$ (1≤xi,yi≤n$1/le x_i, y_i/le 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.

Output

You should print k lines. i-th of these lines must start with an integer ci(1≤ci≤⌈2nk⌉)$c_i (1/le c_i /le /lceil /frac{2n}{k}/rceil)$— the number of vertices visited by i-th clone, followed by ci$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.

题意

给定一个 n 个点 m 条边的无向图，k 个人每秒均可以从一个点到达直接相连的另一个点，问 k 个人每个人最多可以沿特定路径经过 ⌈2nk⌉$/lceil /frac{2n}{k}/rceil$ 个点，能够使得最终图中 n 个点都至少被一个人遍历过？同时要求给出每个人的具体路径走法。

分析

一个借用了深搜的思维题。

对一个图进行深搜 n 个点，统计深搜过的点的次数，最多不会超过 2n 个（包括回溯）。 ∵⌈2nk⌉×k≥2n$/because /lceil /frac{2n}{k} /rceil /times k /ge 2n$ 可以总共遍历点大于 2n 。故以某个点为起点进行深搜，保存深搜的路径。之后将深搜获得的路径分配给 k 个人即可。

注意： 即使深搜出的路径点不足 ⌈2nk⌉$/lceil/frac{2n}{k}/rceil$ 个，最后多余的人仍至少需要到达一个点。

代码