Description:

soda has a computer network consisting of n nodes numbered 1 through n. There are links in the network that connect pairs of nodes. A pair of nodes may have multiple links between them, but no node has a link to itself. A link can only transmit in a single direction.

For two nodes x and y, if both x and y can transmit to each other (perhaps through some intermediate nodes), then x and y are in the same group.

soda wants to increase the number of groups in the network by deleting a link. You need to tell him which link 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≤10^{5},1≤m≤2×10^{5}), the number of nodes and the number links.

Next m lines contain two integers each, ui and vi (1≤ui,vi≤n,ui≠vi), indicating there is a link between nodes ui and vi and the direction is from ui to vi.

Output:

For each test case, output binary string of length m. The i-th character is '1' if soda can delete i-th link to increase the number of groups, otherwise the i-th character is '0'.

Sample Input:

1 3 4 1 2 2 3 3 1 2 1

Sample Output:

1110

Hint:

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

Source:

Submit