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 \le n \le 10^5, 1 \le m \le 2 \times 10^5)$, the number of nodes and the number links.
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 a link between nodes $u_i$ and $v_i$ and the direction is from $u_i$ to $v_i$.

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

zimpha@zju

2015 Multi-University Training Contest 6