Problem Description

Given a simple directed graph $G$ with $n$ vertices and $m$ edges, where vertices are numbered from $1$ to $n$. A simple directed graph is defined as a directed graph with no duplicate edges or self-loops.

A vertex $r$ is defined as the root of the directed graph $G$ if and only if for $1 \leq k \leq n$, there exists exactly one simple directed path from vertex $r$ to vertex $k$. A simple directed path is defined as a path that does not pass through any repeated vertices.

The classification of each vertex is defined as follows:
- If vertex $r$ is the root of graph $G$, it is called a Type 1 vertex.
- If vertex $r$ is not a Type 1 vertex, and there exists a way to remove edges such that the resulting graph $G'$ satisfies: all Type 1 vertices in $G$ are roots in $G'$, and vertex $r$ is also a root in $G'$, then vertex $r$ is called a Type 2 vertex.
- If vertex $r$ does not satisfy the above conditions, it is called a Type 3 vertex.

According to the above definitions, each vertex in graph $G$ belongs to exactly one of the three types: Type 1, Type 2, or Type 3. You need to determine which type each of the vertices $1$ through $n$ belongs to.

Input Format

This problem contains multiple test cases.

The first line of input contains a non-negative integer $c$, indicating the test point number. $c = 0$ indicates that this test point is a sample case.

The second line contains a positive integer $t$, indicating the number of test cases.

The following lines describe each test case:

The first line of each test case contains two positive integers $n$ and $m$, representing the number of vertices and edges in the directed graph, respectively.

The next $m$ lines, each containing two positive integers $u$ and $v$, represent a directed edge from $u$ to $v$. It is guaranteed that $1 \leq u, v \leq n$ and the given directed graph $G$ does not have duplicate edges or self-loops.

Output Format

For each test case, output a line containing a string $s$ of length exactly $n$ indicating the type of each vertex. Here, $s_i = 1$ indicates that vertex $i$ is a Type 1 vertex, $s_i = 2$ indicates that vertex $i$ is a Type 2 vertex, and $s_i = 3$ indicates that vertex $i$ is a Type 3 vertex.

Sample Input and Output

Input Sample #1

0
2
4 7
2 1
4 1
1 4
2 3
3 4
2 4
4 3
4 5
1 2
2 3
2 4
3 1
4 3

Output Sample #1

3233
2211

Input Sample #2

See graphee2.in/ans
This sample satisfies the constraints of test point 2

Output Sample #2

Input Sample #3

See graphee3.in/ans
This sample satisfies the constraints of test points 3,4

Output Sample #3

Input Sample #4

See graphee4.in/ans
This sample satisfies the constraints of test points 5,6

Output Sample #4

Input Sample #5

See graphee5.in/ans
This sample satisfies the constraints of test points 8,9

Output Sample #5

Input Sample #6

See graphee6.in/ans
This sample satisfies the constraints of test points 14,15

Output Sample #6

Notes/Hints

[Sample 1 Explanation]

Sample 1 contains two test cases.

For the first test case, the input graph is as follows:

Since vertices $1, 3, 4$ do not have paths to vertex $2$, they are all Type 3 vertices. Vertex $2$ has three simple directed paths to vertex $1$: $2 \to 1$, $2 \to 4 \to 1$, and $2 \to 3 \to 4 \to 1$, so it is not a Type 1 vertex. By removing edges $1 \to 4$, $4 \to 1$, $3 \to 4$, and $4 \to 3$, vertex $2$ has a unique simple directed path to vertices $1, 3, 4$, making it a root in $G'$, thus a Type 2 vertex.

For the second test case, the input graph is as follows:

It is easy to see that vertices $3, 4$ are Type 1 vertices. By removing edge $2 \to 3$, each vertex has a unique simple directed path to all other vertices, making vertices $1, 2$ Type 2 vertices.

[Data Range]

For all test data, it is guaranteed that: $1 \leq t \leq 10$, $2 \leq n \leq 10^5$, $1 \leq m \leq 2 \times 10^5$, and the graph $G$ does not have duplicate edges or self-loops.

• Special Property A: No Type 1 vertices exist.
• Special Property B: No Type 2 vertices exist.
• Special Property C: The vertex numbered 1 is a Type 1 vertex in graph $G$.

见题面 Input 部分

见题面 Output 部分