CF780E Underground Lab

邪恶的 Bumbershoot 公司在一个巨大的地下实验室里制造克隆人来进行可怕的实验。有一次，该公司克隆了一个比他的同伴更聪明的男孩安德里沙。安德里沙很快意识到，这个实验室发生了一些蹊跷的事情。他召集了克隆人同伴们去与邪恶的守卫兵团斗争。于是他们开始寻找实验室的出口。守护兵团不得不摧毁实验室的建筑群。 实验室可以看作是一个有 $n$ 个顶点和 $m$ 条边的无向图，$k$ 个安德里沙的克隆人同伴开始在一些顶点中寻找出口。每个克隆人每秒可以在任何顶点之间穿越一次，并且允许在任意一个顶点存在任何数量的克隆人。这些克隆人可以在任何时候停止寻找，但他在他的起始顶点必须寻找。出口可以位于实验室的任何一顶点，因此每个顶点必须至少有一个克隆人访问。 在实验室爆炸之前，每个克隆人最多只能访问 $\left\lceil\dfrac{2n}{k}\right\rceil$ 个顶点。 你的任务是选择起始顶点和克隆人的搜索路线。 每条路线可以有最多 $\left\lceil\dfrac{2n}{k}\right\rceil$ 个顶点。

无

无

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.