Bipartite Graph

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.

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

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

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

11111
11100

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

zimpha@zju

2015 Multi-University Training Contest 6