B. Odd Cycle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed graph $$$G$$$ consisting of $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$. An odd cycle is defined as a sequence of vertices (not necessarily distinct) $$$p_0,p_1,\ldots,p_m$$$, such that $$$m$$$ is odd, and there exists a directed edge from vertex $$$p_i$$$ to $$$p_{i+1}$$$ for every $$$0 \le i \lt m$$$.

For each vertex $$$u$$$, determine whether $$$u$$$ is contained in at least one odd cycle.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$), representing the number of vertices and the number of edges in $$$G$$$, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), representing a directed edge from $$$u$$$ to $$$v$$$. $$$G$$$ may contain self loops and multiple edges.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases each do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a line containing a binary string $$$s$$$ of length $$$n$$$. For every $$$1 \le i \le n$$$, if vertex $$$i$$$ is contained in at least one odd cycle, then $$$s_i=$$$ 1; otherwise, $$$s_i=$$$ 0.

Example
Input
7
1 0
3 3
1 2
2 3
3 1
2 2
1 1
2 2
4 4
1 2
2 3
3 4
4 1
2 3
1 2
2 2
2 1
8 8
1 2
2 3
3 1
4 5
5 4
5 6
6 5
7 7
9 14
1 4
4 2
2 5
5 3
3 6
6 1
1 2
7 8
8 7
8 9
9 8
2 4
4 6
6 2
Output
0
111
11
0000
11
11100010
111111000