意大利有$$$n$$$大城市,城市之间有$$$m$$$火车路线。每条路线双向连接两个不同的城市。此外,乘坐火车可以从任何其他城市出发到达每个城市。
目前,所有航线均由政府拥有的意大利运输客运公司运营,但政府希望将这些航线私有化。政府不想赋予单个公司太多权力,但也不想让人们购买很多不同的订阅服务。此外,它希望为所有公司提供公平的机会。为了形式化所有这些愿望,提出了以下模型。
将有 $$$k \ge 2$$$ 私营公司,索引为 $$$1, \, 2, \, \dots, \, k$$$。每条火车路线都将由 $$$k$$$ 公司之一运营。然后:
- 对于任何公司,都应该存在两个城市,使得仅使用该公司运营的路线不可能从另一个城市到达另一个城市。
- 另一方面,对于任何两家公司,应该可以仅使用这两家公司运营的路线从任何其他城市到达每个城市。
找到满足所有这些标准的计划。可以证明,可行的计划总是存在的。请注意,您可以选择数字$$$k$$$,并且不必最小化或最大化它。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 50$$$, $$$n-1 \le m \le n(n-1)/2$$$) — 城市数量和火车路线数量。
接下来的 $$$m$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — 第 $$$i$$$ 条火车路线连接城市 $$$u_i$$$ 和 $$$v_i$$$。
保证路线连接 $$$m$$$ 个不同的城市对。保证乘坐火车可以从任何其他城市出发到达每个城市。
所有测试用例的 $$$n$$$ 值的总和不超过 $$$5000$$$。
输出
对于每个测试用例,在第一行打印一个整数 $$$k$$$ ($$$2 \le k \le m$$$) — 计划中的公司数量;在第二行打印 $$$m$$$ 整数 $$$c_1, \, c_2, \, \dots, \, c_m$$$ ($$$1 \le c_i \le k$$$) — 在你的计划公司 $$$c_i$$$ 中运营第 $$$i$$$ 条路线。
如果有多个有效计划,您可以打印其中任何一个。
示例
输入 #1
2 5 9 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 3 3 1 2 3 1 2 3
输出 #1
4 1 2 3 1 4 2 2 4 3 3 2 3 1
注意
在第一个测试用例中,输出如下图所示,其中不同的颜色对应不同的公司(蓝色代表$$$1$$$,红色代表$$$2$$$,绿色代表$$$3$$$,黄色代表$$$4$$$):
例如,如果我们仅考虑 $$$2$$$ 和 $$$3$$$ 公司,我们可以看到从任何城市都可以到达其他所有城市(下左图)。然而,如果我们仅限制公司$$$2$$$,则不可能从城市$$$1$$$到达城市$$$5$$$(右图)。
在第二个测试用例中,输出如下图所示: