P10790 [NOI2024] Tree Graph.

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

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.

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

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

**[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} | Test Point ID | $t\leq$ | $n\leq$ | $m\leq$ | Special Property | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $3$ | $10$ | $20$ | None | | $2$ | $10$ | $10^3$ | $2000$ | A | | $3,4$ | ^ | ^ | ^ | B | | $5,6$ | ^ | ^ | ^ | None | | $7$ | ^ | $10^5$ | $2\times 10^5$ | A | | $8,9$ | ^ | ^ | ^ | BC | | $10\sim 13$ | ^ | ^ | ^ | B | | $14,15$ | ^ | ^ | ^ | C | | $16\sim 20$ | ^ | ^ | ^ | None | - 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