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.
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$.
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$.