Mila 和 Laura 在网上认识很久了，但从未在现实中见过面。目前，她们都在参加同一个线下活动，这意味着她们一定会见面。然而，她们下榻的酒店非常大且令人困惑。因此，几天过去了，她们仍然没有遇到彼此。

酒店由 $N$ 个房间组成，编号为 $0$ 到 $N - 1$。每个房间都有一盏可以改变颜色的灯。你找到了酒店的电气服务室，可以改变灯的颜色。你的目标是通过灯光引导 Mila 和 Laura，最终让她们见面。

酒店可以表示为一个包含 $N$ 个顶点（房间）和 $M$ 条边（连接房间的走廊）的图。Mila 和 Laura 最初在两个不同的房间，但你不知道具体是哪两个。你可以进行若干次移动。每次移动包括打印一个包含 $N$ 个整数的列表 $c_0, c_1, \dots, c_{N-1}$，这意味着对于每个 $i = 0, 1, \dots, N - 1$，房间 $i$ 的灯的颜色变为 $c_i$。随后，Mila 和 Laura 会查看她们当前所在房间的灯的颜色，并走到一个灯的颜色相同的相邻房间。如果没有这样的相邻房间，她们会留在原地。如果有多个这样的相邻房间，她们会任意选择一个。

如果在你进行移动的过程中，Mila 和 Laura 在任何时刻处于同一个房间或使用了同一条走廊，你就成功地让她们见面了。你最多可以进行 $20\,000$ 次移动，但如果你使用的移动次数越少，得分就越高。

注意，你不知道 Mila 和 Laura 从哪个房间开始，也不知道如果她们有多个颜色相同的房间可供选择时她们会如何行走。你的方案必须在任何起始房间和任何行走方式下都是正确的。

输入格式

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

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

输出格式

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

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

数据范围

• $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 \neq v_i$
• 你可以从任意房间到达其他任何房间。此外，没有从房间到自身的走廊，且任意一对房间之间不存在多条走廊。
• 你最多可以使用 $20\,000$ 次移动（即 $K \le 20\,000$）。

你的方案将在多组测试数据上进行测试，每组测试数据都有相应的分值。每组测试数据包含若干个测试用例。要获得某组测试数据的分数，你需要解决该组中的所有测试用例。

对于你的程序正确解决的每一组测试数据，你将根据以下公式获得分数：

$$\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$ 次。

样例

样例是一个长度为 $3$ 的路径，因此它可以属于第 $3, 4$ 或 $5$ 组测试数据。如果房间的灯光颜色按照样例输出进行设置，那么 Mila 和 Laura 将一定会见面。

上图展示了样例的前四次移动。

输入 1

3 2
0 1
1 2

输出 1

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