意大利有 $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 \neq 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$)，表示在你的方案中，第 $i$ 条线路由公司 $c_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（下图右侧）。

在第二个测试用例中，输出方案的示意图如下：