Jump Trading 计划使用分布在全球的服务器网络进行高频交易（HFT）。

一个网络由 $N$ 台服务器和 $M$ 条通信链路组成。每台服务器用 $1$ 到 $N$ 之间的一个整数标识，每条通信链路用 $1$ 到 $M$ 之间的一个整数标识。任意给定的两台服务器之间最多只有一条通信链路直接相连。有趣的是，使用通信链路的交易只能单向进行。最初，每条通信链路的方向尚未确定，且在不考虑方向的情况下，所有服务器都通过一条或多条通信链路直接或间接相连。

最小化网络延迟是高频交易的关键组成部分。为了实现这一目标，Jump Trading 希望确定所有通信链路的方向，以配置一个具有低传输深度的网络。最终的网络必须满足以下条件：

• 对于每台服务器，使用一条或多条通信链路可以直接或间接到达的服务器数量小于或等于 $2$。

确定是否存在满足要求的网络配置，如果存在，请构造它。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。($1 \le T \le 100$)

每个测试用例的第一行包含两个空格分隔的整数 $N$ 和 $M$，分别表示服务器的数量和通信链路的数量。($2 \le N \le 1\,000$；$1 \le M \le 2\,000$)

接下来的 $M$ 行中，第 $i$ 行包含两个空格分隔的整数 $U_i$ 和 $V_i$，表示第 $i$ 条通信链路连接的两台服务器的编号。($1 \le U_i, V_i \le N$；$U_i \ne V_i$)

任意给定的两台服务器之间最多只有一条通信链路直接相连，且如果忽略方向，所有服务器都通过一条或多条通信链路直接或间接相连。

输出格式

按顺序输出 $T$ 行，每行对应一个测试用例。

对于每个测试用例，如果不存在满足要求的网络配置，则输出 -1。

如果可以配置一个满足条件的网络，则输出 $M$ 个空格分隔的整数。如果第 $i$ 条通信链路的方向被设置为正向（$U_i \to V_i$），则第 $i$ 个整数应为 0；如果为反向（$V_i \to U_i$），则为 1。只要满足题目描述中的条件，任何合法的网络配置都将被接受。

样例

输入样例 1

3
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1
5 5
1 2
2 3
3 4
4 5
5 1

输出样例 1

1 1 1
0 1 0 1
-1

输入样例 2

1
4 5
1 2
1 3
1 4
2 4
3 4

输出样例 2

1 1 0 0 0

输入样例 3

1
12 12
1 2
2 3
3 1
1 4
1 5
2 6
2 7
1 8
8 9
9 10
10 11
10 12

输出样例 3

1 1 0 1 1 1 1 1 0 1 1 1