题目描述

题目译自 European Girls' Olympiad in Informatics 2024 Day2 T4. Make them Meet

米拉和劳拉是多年的网友，从未在现实中见过面。现在，她们同时参加一个线下活动，注定会相遇。然而，她们下榻的酒店非常大且复杂，几天过去了，你发现她们仍然没有偶遇。

酒店有 $N$ 个房间，编号从 $0$ 到 $N-1$，每个房间有一盏可以变换颜色的灯。你找到了酒店的电气服务室，可以改变灯的颜色。你的目标是通过调整灯的颜色引导米拉和劳拉，让她们最终相遇。

酒店可以看作一个图，包含 $N$ 个顶点（房间）和 $M$ 条边（连接房间的走廊）。米拉和劳拉初始在两个不同的房间，但你不知道她们的具体位置。你可以进行若干次操作，每次操作输出 $N$ 个整数 $c_0, c_1, \ldots, c_{N-1}$，表示将房间 $i$ 的灯颜色设为 $c_i$（$i = 0, 1, \ldots, N-1$）。米拉和劳拉会查看当前房间灯的颜色，并走向一个灯颜色相同的相邻房间。如果没有这样的相邻房间，她们会留在原地。如果有多个符合条件的相邻房间，她们会随机选择一个。

如果米拉和劳拉在你的操作过程中某时刻处于同一房间或同时经过同一条走廊，你就成功让她们相遇。你最多可以进行 $20000$ 次操作，但操作次数越少，分数越高。

注意，你不知道米拉和劳拉的起始房间，也不知道她们在多个同色房间可选时会如何选择。你的方案必须在任何起始房间和任何行走选择下都正确。

输入格式

第一行包含两个整数 $N, M$，分别表示酒店的房间数和走廊数。

接下来的 $M$ 行每行包含两个整数 $u_i, v_i$，表示房间 $u_i$ 和 $v_i$ 之间有一条走廊。

输出格式

输出一行，包含一个整数 $K$，表示操作次数。

接下来的 $K$ 行，每行输出 $N$ 个整数 $c_0, c_1, \ldots, c_{N-1}$，满足 $0 \leq c_i \leq N$，按时间顺序表示你的操作。

3 2
0 1
1 2

5
2 2 2
2 2 3
2 2 3
1 2 2
1 2 2

样例是一个长度为 $3$ 的路径，可能属于测试组 $3$、$4$ 或 $5$。如果按照样例输出的方式设置房间灯的颜色，米拉和劳拉总会相遇。

例如，假设米拉从房间 $0$ 开始，劳拉从房间 $1$ 开始：

• 第一次操作：米拉必须走向房间 $1$。如果劳拉走向房间 $0$，她们会在 $0$ 和 $1$ 之间的走廊相遇。假设劳拉走向房间 $2$。
• 第二次操作：米拉走回房间 $0$，劳拉留在房间 $2$。
• 第三次操作：米拉再次走向房间 $1$，劳拉留在房间 $2$。
• 第四次操作：米拉走向房间 $2$，劳拉走向房间 $1$。她们会在 $1$ 和 $2$ 之间的走廊相遇。
• 第五次操作：米拉和劳拉交换位置并再次相遇（但已无关紧要，因为她们已相遇）。

下图展示了样例的前四次操作。

注意，这仅是她们从房间 $0$ 和 $1$ 开始的情况。可以验证，相同的操作序列能确保她们无论从何处开始或如何行走都会相遇。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 100$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $0 \leq u_i, v_i \leq N-1$，且 $u_i \neq v_i$
• 从任意房间可以到达其他任意房间。此外，没有从房间到自身的走廊，也没有任意两个房间之间的多条走廊。
• 你最多可进行 $20000$ 次操作（即 $K \leq 20000$）。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$10$	$M = N-1$，且走廊为 $(0,1), (0,2), (0,3), \ldots, (0, N-1)$，即图为星形图
$2$	$13$	$M = \frac{N(N-1)}{2}$，即任意两个房间之间有走廊，图为完全图
$3$	$11$	$M = N-1$，且走廊为 $(0,1), (1,2), (2,3), \ldots, (N-2, N-1)$，即图为路径图
$4$	$36$	$M = N-1$，即图为树
$5$	$30$	无附加限制

对于每个正确解决的子任务，你将根据以下公式获得分数：

$$\text{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$ 的关系。