题目描述

帕查先生是一位玻利维亚考古学家，他在蒂瓦纳库附近发现了一份描述蒂瓦纳库时期（公元300-1000年）世界的古老文献。当时有 $N$ 个国家，编号从1到 $N$。

文献中列出了 $M$ 对不同的相邻国家：

$$\begin{aligned}(A[0], B[0]), (A[1], B[1]), \ldots, (A[M - 1], B[M - 1])\end{aligned} $$

对于每个 $i$（$0 \leq i < M$），文献表明国家 $A[i]$ 与 $B[i]$ 相邻，反之亦然。未列出的国家对则不相邻。

帕查先生想要绘制一幅世界地图，使得所有国家之间的相邻关系完全符合蒂瓦纳库时期的情况。为此，他首先选择一个正整数 $K$，然后将地图绘制为 $K \times K$ 的方格网格，行从0到 $K-1$ 编号（从上到下），列从0到 $K-1$ 编号（从左到右）。

他想用 $N$ 种颜色中的一种给地图的每个单元格上色。颜色编号从1到 $N$，国家 $j$（$1 \leq j \leq N$）由颜色 $j$ 表示。上色必须满足以下所有条件：

• 对于每个 $j$（$1 \leq j \leq N$），至少有一个单元格是颜色 $j$。
• 对于每对相邻国家 $(A[i], B[i])$，至少有一对相邻单元格，其中一个是颜色 $A[i]$，另一个是颜色 $B[i]$。两个单元格相邻是指它们共享一条边。
• 对于每对颜色不同的相邻单元格，这两种颜色所代表的国家在蒂瓦纳库时期是相邻的。

例如，如果 $N=3$，$M=2$，相邻国家对为 $(1,2)$ 和 $(2,3)$，那么 $(1,3)$ 不相邻，下面这个 $K=3$ 的地图满足所有条件。

:::align{center} :::

特别地，一个国家在地图上不需要形成一个连通区域。在上面的地图中，国家3形成了一个连通区域，而国家1和2形成了不连通区域。

你的任务是帮助帕查先生选择一个 $K$ 值并创建一幅地图。文献保证这样的地图存在。由于帕查先生更喜欢较小的地图，在最后一个子任务中，你的得分取决于 $K$ 的值，较小的 $K$ 可能会带来更好的分数。然而，并不要求找到最小可能的 $K$ 值。

实现细节

你需要实现以下函数：

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)

• $N$：国家的数量。
• $M$：相邻国家对的数量。
• $A$ 和 $B$：长度为 $M$ 的数组，描述相邻的国家。

该函数每个测试用例最多被调用50次。

该函数应返回一个表示地图的数组 $C$。设 $K$ 为 $C$ 的长度。

• $C$ 的每个元素都是一个长度为 $K$ 的数组，包含1到 $N$ 之间的整数。
• $C[i][j]$ 是第 $i$ 行第 $j$ 列单元格的颜色（对于 $0 \leq i, j < K$）。
• $K$ 必须小于或等于240。

输入格式

T
N M
A[0] B[0]
:
A[M-1] B[M-1]
...

其中 $T$ 是场景的数量。

输出格式

P
Q[0] Q[1] ... Q[P-1]

C[0][0] ... C[0][Q[0]-1]
:
C[P-1][0] ... C[P-1][Q[P-1]-1]

其中 $P$ 是 create_map 返回的数组 $C$ 的长度，$Q[i]$（$0 \leq i < P$）是 $C[i]$ 的长度。注意，输出格式中的第3行特意留空。

输入输出样例 #1

输入 #1

3 2
1 2
2 3

输出 #1

3
3 3 3
2 3 3
2 3 2
1 2 1

输入输出样例 #2

输入 #2

4 4
1 2
1 3
2 4
3 4

输出 #2

7
7 7 7 7 7 7 7
2 1 3 3 4 3 4
2 1 3 3 3 3 3
2 1 1 1 3 4 4
2 2 2 1 3 4 3
1 1 1 2 4 4 4
2 2 1 2 2 4 3
2 2 1 2 2 4 4

说明/提示

示例1

考虑以下调用：

create_map(3, 2, [1, 2], [2, 3])

这是任务描述中的例子，因此该函数可以返回以下地图：

[
[2, 3, 3],
[2, 3, 2],
[1, 2, 1]
]

示例2

考虑以下调用：

create_map(4, 4, [1, 1, 2, 3], [2, 3, 4, 4])

在这个例子中，$N=4$，$M=4$，国家对 $(1,2)$、$(1,3)$、$(2,4)$ 和 $(3,4)$ 是相邻的。因此，$(1,4)$ 和 $(2,3)$ 不相邻。

该函数可以返回一个 $K=7$ 的地图，满足所有条件：

[
[2, 1, 3, 3, 4, 3, 4],
[2, 1, 3, 3, 3, 3, 3],
[2, 1, 1, 1, 3, 4, 4],
[2, 2, 2, 1, 3, 4, 3],
[1, 1, 1, 2, 4, 4, 4],
[2, 2, 1, 2, 2, 4, 3],
[2, 2, 1, 2, 2, 4, 4]
]

这个地图可以更小，例如，该函数可以返回一个 $K=2$ 的地图：

[
[3, 1],
[4, 2]
]

注意这两个地图都满足 $K/N \leq 2$。

子任务和评分

子任务	分值	附加约束
1	5	$M = N - 1$，对于每个 $0 \leq i < M$，$A[i] = i + 1$，$B[i] = i + 2$。
2	10	$M = N - 1$
3	7	$M = \frac{N \cdot (N - 1)}{2}$
4	8	国家1与所有其他国家相邻。可能还有其他相邻的国家对。
5	14	$N \leq 15$
6	56	无附加约束。

在子任务6中，你的得分取决于 $K$ 的值。

• 如果 create_map 返回的任何地图不满足所有条件，你在该子任务的得分将为0。
• 否则，设 $R$ 为所有 create_map 调用中 $K/N$ 的最大值。然后，你将根据以下表格获得部分分数：

限制	分值
$6 < R$	$0$
$4 < R \leq 6$	$14$
$3 < R \leq 4$	$28$
$2.5 < R \leq 3$	$42$
$2 < R \leq 2.5$	$49$
$R \leq 2$	$56$