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≤n,m≤105), the number of vertices and the number of edges.

Next m lines contain two integers each, ui and vi (1≤ui,vi≤n,ui≠vi) , 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:

Submit