伯兰有 $$$n$$$ 个城市,其中一些有道路相连。每条道路都是双向的,连接两个不同的城市,并且每两个城市最多有一条道路连接它们。
Berland 总统决定将国家分为 $$$r$$$ 州,每个城市都属于这些 $$$r$$$ 州之一。
分割后,每条道路将连接同一州的城市或不同州的城市。我们将连接同一州的两个城市的道路称为“内部”道路。
总统不喜欢奇怪的人、奇怪的城市和奇数的数字,因此他希望这种分割以这样的方式进行:每个城市都有偶数条“内部”道路与其相连。
请帮助总统找到存在这种分割的最小可能 $$$r$$$。
输入
输入包含一个或多个测试用例。第一个输入行包含一个整数 $$$t$$$ — 测试用例的数量。然后,$$$t$$$ 测试用例如下。单独解决测试用例,测试用例完全独立,互不影响。
然后是 $$$t$$$ 输入数据块。每个块从空行开始,该空行将其与剩余的输入数据分开。每个块的第二行包含两个空格分隔的整数 $$$n$$$, $$$m$$$ ($$$1 \le n \le 2000$$$, $$$0 \le m \le 10000$$$) — Berland 的城市数量和道路数量。接下来的 $$$m$$$ 行包含两个以空格分隔的整数 — $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$),表示第 $$$i$$$ 条道路连接城市 $$$x_i$$$ 和$$$y_i$$$。每对城市最多由一条道路连接。
所有测试用例的 $$$n$$$ 值总和不超过 $$$2000$$$。所有测试用例的值 $$$m$$$ 总和不超过 $$$10000$$$。
输出
对于每个测试用例,首先打印一行包含单个整数 $$$r$$$ — 需要分割的最小可能状态数。在下一行中打印 $$$n$$$ 以空格分隔的整数,范围从 $$$1$$$ 到 $$$r$$$(含),其中第 $$$j$$$ 个数字表示第 $$$j$$$ 个城市的州号。如果有多个解决方案,请打印其中一个。
示例
输入 #1
2 5 3 1 2 2 5 1 5 6 5 1 2 2 3 3 4 4 2 4 1
输出 #1
1 1 1 1 1 1 2 2 1 1 1 1 1