Bipartite Graph

Problem Description

soda has a undirected graph with $n$ vertices and $m$ edges. He wants to make the graph become a bipartite graph by deleting only one vertex. You need to tell him which vertex can be deleted.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case: The first contains two integer $n$ and $m$ $(1 \le n, m \le 10^5)$, the number of vertices and the number of edges. Next $m$ lines contain two integers each, $u_i$ and $v_i$ $(1 \le u_i,v_i \le n, u_i \ne v_i)$ , indicating there is an edge between vertices $u_i$ and $v_i$.

Output

For each test case, output binary string of length $n$. The $i$-th character is '1' if soda can delete $i$-th vertex to make the graph become a bipartite graph, otherwise the $i$-th character is '0'.

Sample Input

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

Sample Output

11111
11100

Hint

If you need a larger stack size, please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6