在国际象棋城（Chess City）里有 $n$ 个朋友和 $n$ 栋房子，编号均为 $1$ 到 $n$，其中朋友 $i$ 住在房子 $i$ 中。房子之间由 $m$ 条双向道路连接，形成一个连通的网络。

国际象棋城还有 $n$ 个虚拟象棋俱乐部，编号为 $1$ 到 $n$。每个朋友必须选择加入恰好一个俱乐部。这些选择不需要互不相同，因此某些俱乐部可能没有任何成员。

当朋友 $i$ 举办象棋派对时，所有与朋友 $i$ 属于同一个俱乐部且住在与房子 $i$ 直接有道路相连的房子里的朋友都会参加。如果参加派对的总人数（包括朋友 $i$ 本人）是偶数，则认为该派对是成功的；在这种情况下，他们可以同时两两对弈。

为每个朋友选择一个俱乐部，使得每个朋友的派对都是成功的，或者报告无解。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示房子的数量和道路的数量 ($2 \le n \le 10^5$；$n - 1 \le m \le 2 \cdot 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$，描述连接房子 $u$ 和 $v$ 的一条双向道路 ($1 \le u, v \le n$；$u \neq v$)。任意两栋房子之间最多只有一条道路连接。保证可以通过道路从任意一栋房子到达其他任意一栋房子。

保证所有测试用例中 $n$ 的总和不超过 $10^5$，且 $m$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果无法为每个朋友分配一个象棋俱乐部以使每个朋友的派对都成功，则输出一个整数 $-1$。

否则，输出 $n$ 个整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 表示朋友 $i$ 应该加入的象棋俱乐部的编号 ($1 \le c_i \le n$)。如果存在多个答案，输出其中任意一个即可。

样例

输入样例 1

3
2 1
1 2
3 3
1 2
2 3
3 1
8 10
1 2
1 4
1 7
5 2
5 4
5 7
5 3
2 6
2 8
6 8

输出样例 1

1 1
-1
3 3 6 6 6 2 6 2