你最近领养了一些小猫，现在你想为它们建造一个房子。房子的外形是一个有 $N$ 个顶点的凸多边形。房子内部通过 $M$ 条连接顶点的直线段（内墙）分隔成若干个房间。没有任何两条墙会相交，但多个墙可能会连接到同一个顶点。

为什么你的猫屋会如此特别呢？因为在每一个顶点上，你都要建造一根完全由猫薄荷制成的柱子！小猫可以玩耍任何与它们所在房间接触的柱子，这让它们拥有了一个真正的豪华住宅。

为了让房子更令人兴奋，你想使用不同口味的猫薄荷。一根柱子只能使用一种口味，但不同的柱子可以使用不同的口味。这里有一个问题：如果某个房间无法接触到房子里所有的猫薄荷口味，那么那个房间里的小猫会感到被冷落并变得伤心。

你的任务是为每个顶点选择一种猫薄荷口味，使得 (a) 每个房间都能接触到所有的口味，并且 (b) 使用的口味数量尽可能多。

在下面的例子中，三种不同的口味（用红色、绿色和蓝色圆点表示）分布在一个 8 边形的房子里，同时保证了每个房间里的小猫都很开心：

在上图中，从顶墙的左角开始顺时针方向，颜色依次为：绿色、蓝色、红色、红色、蓝色、绿色、蓝色、红色。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例包含三行。第一行给出 $N$ 和 $M$，即猫屋的顶点数和内墙数。第二行给出 $M$ 个空格分隔的整数 $U_1, U_2, \dots, U_M$，描述每条内墙的起点。第三行给出 $M$ 个空格分隔的整数 $V_1, V_2, \dots, V_M$，描述每条内墙的终点。

更准确地说，如果猫屋的顶点按顺时针顺序标记为 $1, 2, \dots, N$，那么内墙位于顶点 $U_1$ 和 $V_1$、$U_2$ 和 $V_2$ 等之间。

输出格式

对于每个测试用例，输出两行。第一行应为 "Case #x: C"，其中 $x$ 是用例编号，$C$ 是可以使用的最大猫薄荷口味数量。第二行应包含 $N$ 个空格分隔的整数："y_1 y_2 ... y_N"，其中 $y_i$ 是一个介于 1 和 $C$ 之间的整数，表示你分配给顶点 $i$ 的猫薄荷口味。

如果有多种使用 $C$ 种口味的分配方案，你可以输出其中任意一种。

数据范围

$1 \le T \le 100$。 $1 \le M \le N - 3$。 $1 \le U_i < V_i \le N$（对于所有 $i$）。 内墙除了在 $N$ 个顶点处外，互不接触。 内墙除了在 $N$ 个顶点处外，不接触房子的外墙。 内存限制：1GB。

小数据集（测试集 1 - 可见；20 分）

$4 \le N \le 8$。 时间限制：3 秒。

大数据集（测试集 2 - 隐藏；25 分）

$4 \le N \le 2000$。 时间限制：6 秒。

样例

输入 1

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

输出 1

Case #1: 3
1 2 1 3
Case #2: 3
1 2 3 1 1 3 2 3