Background

Due to differences in the performance of judging machines, the time limit for this problem is doubled.

Problem Description

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

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

The type of each vertex is defined as follows:

• If vertex $r$ is a root of graph $G$, then vertex $r$ is called a type-1 vertex of graph $G$.
• If vertex $r$ is not a type-1 vertex of graph $G$, and there exists a way to delete edges such that the graph $G'$ obtained after deleting some edges from $G$ satisfies: all type-1 vertices in $G$ are roots of $G'$, and vertex $r$ is also a root of $G'$, then vertex $r$ is called a type-2 vertex of graph $G$.
• If vertex $r$ does not satisfy the above conditions, then vertex $r$ is called a type-3 vertex of graph $G$.

According to the definitions above, every 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 vertex $1\sim n$ belongs to.

Input Format

This problem has multiple test cases.

The first line contains a non-negative integer $c$, indicating the test point ID. $c=0$ means this test point is a sample.

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

Then follow the test cases one by one. For each test case:

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

The next $m$ lines each contain two positive integers $u,v$, representing a directed edge from $u$ to $v$. It is guaranteed that $1\leq u,v\leq n$, and the given directed graph $G$ has no multiple edges and no self-loops.

Output Format

For each test case, output one line containing a string $s$ of length exactly $n$, representing the type of each vertex. Here $s_i=1$ means vertex $i$ is a type-1 vertex, $s_i=2$ means vertex $i$ is a type-2 vertex, and $s_i=3$ means vertex $i$ is a type-3 vertex.

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

3233
2211

见 graphee2.in/ans
这个样例满足测试点 2 的约束条件

见 graphee3.in/ans
这个样例满足测试点 3,4 的约束条件

见 graphee4.in/ans
这个样例满足测试点 5,6 的约束条件

见 graphee5.in/ans
这个样例满足测试点 8,9 的约束条件

见 graphee6.in/ans
这个样例满足测试点 14,15 的约束条件

Hint

[Sample 1 Explanation]

Sample $1$ contains two test cases.

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

Since $1,3,4$ all have no path that can reach $2$, $1,3,4$ are all type-3 vertices. Since there are three directed simple paths from $2$ to $1$: $2\to 1$, $2\to 4\to 1$, $2\to 3\to 4\to 1$, vertex $2$ is not a type-1 vertex. After deleting edges $1\to 4$, $4\to 1$, $3\to 4$, $4\to 3$, the directed simple path from $2$ to each of $1,3,4$ becomes unique, so $2$ is a root of graph $G'$, i.e. $2$ is a type-2 vertex.

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

It is easy to see that $3,4$ are both type-1 vertices. After deleting edge $2\to 3$, the directed simple path from every vertex to every other vertex is unique, so $1,2$ are both type-2 vertices.

[Constraints]

For all test cases, it is guaranteed that $1\leq t\leq 10$, $2\leq n\leq 10^5$, $1\leq m\leq 2\times 10^5$, and graph $G$ has no multiple edges and no self-loops.

::cute-table{tuack}

• Special Property A: It is guaranteed that there are no type-1 vertices.
• Special Property B: It is guaranteed that there are no type-2 vertices.
• Special Property C: It is guaranteed that vertex $1$ is a type-1 vertex of graph $G$.

Translated by ChatGPT 5