Group

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.

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⁵,1≤m≤2×10⁵), 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.

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

1
3 4
1 2
2 3
3 1
2 1

1110

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

2015 Multi-University Training Contest 6