odd doctor 已更新

Bipartite Graph

Time Limit
5s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(1/1)
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 (1n,m105), the number of vertices and the number of edges.
Next m lines contain two integers each, ui and vi (1ui,vin,uivi) , indicating there is an edge between vertices ui and vi.

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

Source:

2015 Multi-University Training Contest 6


Submit