P10851 [EGOI 2024] Make Them Meet / 活动面基

Day 2 Problem D. 题面译自 [EGOI2024 makethemmeet](https://wiki.egoi2024.nl/tasks/makethemmeet/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。 **警告：滥用本题评测将会封号。**

Mila 和 Laura 在网上已经是很长时间的朋友了；但她们从未在现实中见过面。现在，她们都参加了同一个现场活动，这意味着她们肯定会见面。然而，她们所住的酒店非常大且复杂。因此，经过几天后，她们仍未碰面。 酒店由 $N$ 个房间组成，编号从 $0$ 到 $N - 1$。每个房间都有一个可以更换颜色的灯。你找到了酒店的电力服务房，允许你改变灯的颜色。你的目标是使用这些灯引导 Mila 和 Laura 最终见面。 酒店可以表示为一个有 $N$ 个顶点（房间）和 $M$ 条边（连接房间的走廊）的图。Mila 和 Laura 最初在两个不同的房间开始，但你不知道是哪些房间。你可以进行若干次移动。每次移动包括打印一个包含 $N$ 个整数的列表 $c_0,c_1,\cdots,c_{N-1}$，表示房间 $i$ 的灯变为颜色 $c_i$，其中 $i = 0, 1,\cdots, N - 1$。然后，Mila 和 Laura 会查看她们当前所在房间的灯的颜色，并走向相邻房间中灯颜色相同的房间。如果没有这样的相邻房间，她们将留在原地。如果有多个这样的相邻房间，她们将任意选择一个。 如果在你的移动过程中，Mila 和 Laura 在同一个房间或同时使用同一个走廊，那么你就成功地让她们见面了。你最多可以进行 $2\times 10^4$ 次移动，但如果你使用更少的移动次数，你的得分会更高。 注意，你不知道 Mila 和 Laura 最初在哪个房间，也不知道如果她们有多个相同颜色的房间可以选择时会如何走。**你的解决方案必须在无论她们的起始房间是哪些或如何走动的情况下都是正确的。**

第一行包含两个整数 $N$ 和 $M$，分别表示酒店的房间数和走廊数。 接下来的 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示房间 $u_i$ 和 $v_i$ 由一个走廊连接。

输出一行一个整数 $K$，表示移动次数。 在接下来的 $K$ 行中，每行输出 $N$ 个整数 $c_0,c_1,\cdots,c_{N-1}$，其中对所有的 $i$ 都有 $0 \le c_i \le N$。这 $K$ 行代表按时间顺序的你的移动。

**样例解释** 样例情况是一个长度为 $3$ 的路径，因此它可能属于测试组 $3, 4$ 或 $5$。如果房间的灯根据样例输出进行着色，那么 Mila 和 Laura 总会见面。 例如，假设 Mila 开始在房间 $0$，Laura 开始在房间 $1$： - 第一步：Mila 必须走到房间 $1$。如果 Laura 走到房间 $0$，那么她们将在 $0$ 和 $1$ 之间的走廊上相遇。假设 Laura 走到房间 $2$。 - 第二步：Mila 走回房间 $0$，Laura 留在房间 $2$。 - 第三步：Mila 再次走到房间 $1$，Laura 留在房间 $2$。 - 第四步：Mila 走到房间 $2$，Laura 走到房间 $1$。于是她们将在房间 $1$ 和 $2$ 之间的走廊上相遇。 - 第五步：Mila 和 Laura 交换位置并再次相遇（但这并不重要，因为她们已经见面了）。 下图显示了样例的前四步。  注意，这仅仅是朋友从房间 $0$ 和 $1$ 开始的情况。可以验证，无论她们从哪里开始以及如何行走，相同的移动顺序都能确保她们见面。 --- **数据范围** 对于全部数据，$2\le N\le 100$，$N-1\le M\le \frac{N(N-1)}{2}$，$0\le u_i,v_i\le N-1$ 且 $u_i\ne v_i$。保证你可以从每个房间到达所有房间，且没有走廊连接一个房间和它自己，也没有多个走廊连接相同的两个房间。你最多可以使用 $2\times 10^4$ 步（即 $K\le 2\times 10^4$）。 - 子任务一（至多 $10$ 分）：$M=N-1$ 且走廊是 $(0,1),(0,2),(0,3),\cdots,(0,N-1)$。也就是说，图为菊花图。 - 子任务二（至多 $13$ 分）：$M=\frac{N(N-1)}{2}$，即任意两个房间之间都有一条走廊。也就是说，图为完全图。 - 子任务三（至多 $11$ 分）：$M=N-1$ 且走廊是 $(0,1),(1,2),(2,3),\cdots,(N-2,N-1)$。也就是说，图为一条链。 - 子任务四（至多 $36$ 分）：$M=N-1$。也就是说，图为一棵树。 - 子任务五（至多 $30$ 分）：无特殊限制。 注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。 --- **评分方式** 对于每个你的程序正确解决的子任务，你会根据以下公式获得分数： $$ \textrm{score}=\left\lfloor S_g\cdot\min\left(1,\frac{2000}{K_g+1900}+\frac{1}{5}\right)\right\rfloor $$ 其中 $S_g$ 是这个子任务的满分，$K_g$ 是你的程序在这个子任务的所有测试点中使用的最大步数。这意味着要想得到满分，你需要用不超过 $600$ 步解决每个测试点。下面是得分关于 $K_g$ 的函数图象。