Berland 有 $$$n$$$ 个城市和 $$$m$$$ 双向道路,每条道路连接两个不同的城市。
最近,贝尔兰政府做出了一项艰难的决定,将道路的所有权转让给私营公司。 Berland 总共有 $$$100500$$$ 私营公司,编号从 $$$1$$$ 到 $$$100500$$$ 之间的整数。私有化后,每条路都应该完全属于一家公司。
反垄断委员会要求私有化后每家公司最多可以拥有两条道路。 Berland的城市学家也表达了他们的观点:每个城市应该毗邻至多$$$k$$$公司拥有的道路。
帮助政府在公司之间分配道路,以满足这两个条件。也就是说,每个公司最多有两条道路,每个城市最多有 $$$k$$$ 与其相邻的不同公司的道路。
输入
输入包含一个或多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 300$$$) — 输入中测试用例的数量。单独解决测试用例,测试用例完全独立,互不影响。
以下几行描述了测试用例。每个案例都以由三个空格分隔的整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ 组成的行开始 ($$$2 \le n \le 600$$$, $$$1 \le m \le 600$$$, $$$1 \le k \le n - 1$$$) — 城市数量、道路数量以及与城市相邻的道路的最大多样性。
接下来是 $$$m$$$ 行,每行都有一对空格分隔的整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$; $$$a_i \ne b_i$$$)。这意味着第 $$$i$$$ 条道路连接城市 $$$a_i$$$ 和 $$$b_i$$$。所有道路都是双向的。一对城市之间至多有一条道路。
所有测试用例的 $$$n$$$ 值总和不超过 $$$600$$$。所有测试用例的 $$$m$$$ 值总和不超过 $$$600$$$。
输出
打印 $$$t$$$ 行:第 $$$i$$$ 行应包含第 $$$i$$$ 测试用例的答案。对于测试用例,打印一系列以空格分隔的整数 $$$c_1, c_2, \dots, c_m$$$,其中 $$$c_i$$$ ($$$1 \le c_i \le 100500$$$) 是拥有规划中第 $$$i$$$ 条道路的公司。如果有多个解,输出任意一个。如果测试用例没有解决方案,请打印 $$$c_1=c_2=\ldots=c_m=0$$$。
示例
输入 #1
3 3 3 2 1 2 2 3 3 1 4 5 2 1 2 1 3 1 4 2 3 2 4 4 6 2 1 2 1 3 1 4 2 3 2 4 3 4
输出 #1
1 2 3 2 1 1 2 3 0 0 0 0 0 0