# 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

wange2014

## Source

2015 Multi-University Training Contest 5