MZL's endless loop

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

As we all kown, MZL hates the endless loop deeply, and he commands you to solve this problem to end the loop.
You are given an undirected graph with $n$ vertexs and $m$ edges. Please direct all the edges so that for every vertex in the graph the inequation $|out~degree~-~in~degree|\leq 1$ is satisified.
The graph you are given maybe contains self loops or multiple edges.

Input

The first line of the input is a single integer $T$, indicating the number of testcases.
For each test case, the first line contains two integers $n$ and $m$.
And the next $m$ lines, each line contains two integers $u_i$ and $v_i$, which describe an edge of the graph.
$T\leq 100$, $1\leq n\leq 10^5$, $1\leq m\leq 3*10^5$, $\sum n\leq 2*10^5$, $\sum m\leq 7*10^5$.

Output

For each test case, if there is no solution, print a single line with $-1$, otherwise output $m$ lines,.
In $i$th line contains a integer $1$ or $0$, $1$ for direct the $i$th edge to $u_i\rightarrow v_i$, $0$ for $u_i\leftarrow v_i$.

Sample Input

2 3 3 1 2 2 3 3 1 7 6 1 2 1 3 1 4 1 5 1 6 1 7

Sample Output

1 1 1 0 1 0 1 0 1

Hint

wange2014

Source

2015 Multi-University Training Contest 5

提交代码