CF1547G.How Many Paths?

You are given a directed graph $G$ which can contain loops (edges from a vertex to itself). Multi-edges are absent in $G$ which means that for all ordered pairs $(u, v)$ exists at most one edge from $u$ to $v$. Vertices are numbered from $1$ to $n$.

A path from $u$ to $v$ is a sequence of edges such that:

• vertex $u$ is the start of the first edge in the path;
• vertex $v$ is the end of the last edge in the path;
• for all pairs of adjacent edges next edge starts at the vertex that the previous edge ends on.

We will assume that the empty sequence of edges is a path from $u$ to $u$.

For each vertex $v$ output one of four values:

• $0$, if there are no paths from $1$ to $v$;
• $1$, if there is only one path from $1$ to $v$;
• $2$, if there is more than one path from $1$ to $v$ and the number of paths is finite;
• $-1$, if the number of paths from $1$ to $v$ is infinite.

Let's look at the example shown in the figure.

Then:

• the answer for vertex $1$ is $1$: there is only one path from $1$ to $1$ (path with length $0$);
• the answer for vertex $2$ is $0$: there are no paths from $1$ to $2$;
• the answer for vertex $3$ is $1$: there is only one path from $1$ to $3$ (it is the edge $(1, 3)$);
• the answer for vertex $4$ is $2$: there are more than one paths from $1$ to $4$ and the number of paths are finite (two paths: $[(1, 3), (3, 4)]$ and $[(1, 4)]$);
• the answer for vertex $5$ is $-1$: the number of paths from $1$ to $5$ is infinite (the loop can be used in a path many times);
• the answer for vertex $6$ is $-1$: the number of paths from $1$ to $6$ is infinite (the loop can be used in a path many times).

给你一个有向图 $G$，其中可能包含自环（即从一个顶点指向其自身的边）。图 $G$ 中不存在重边，这意味着对任意有序顶点对 $(u, v)$，至多存在一条从 $u$ 到 $v$ 的边。顶点编号为 $1$ 到 $n$。

从 $u$ 到 $v$ 的一条路径是指满足以下条件的一条边序列：

• 顶点 $u$ 是该路径中第一条边的起点；
• 顶点 $v$ 是该路径中最后一条边的终点；
• 对于任意相邻的两条边，后一条边的起点等于前一条边的终点。

我们约定：空边序列是顶点 $u$ 到自身的一条路径（即长度为 $0$ 的路径）。

对每个顶点 $v$，输出以下四个值之一：

• $0$：若不存在从 $1$ 到 $v$ 的路径；
• $1$：若恰好存在一条从 $1$ 到 $v$ 的路径；
• $2$：若存在多于一条从 $1$ 到 $v$ 的路径，且路径总数有限；
• $-1$：若从 $1$ 到 $v$ 的路径数量无限。

请参考下图所示示例：

则：

• 顶点 $1$ 的答案为 $1$：仅存在一条从 $1$ 到 $1$ 的路径（即长度为 $0$ 的空路径）；
• 顶点 $2$ 的答案为 $0$：不存在从 $1$ 到 $2$ 的路径；
• 顶点 $3$ 的答案为 $1$：仅存在一条从 $1$ 到 $3$ 的路径（即边 $(1, 3)$）；
• 顶点 $4$ 的答案为 $2$：存在多于一条从 $1$ 到 $4$ 的路径，且路径总数有限（共两条：$[(1, 3), (3, 4)]$ 和 $[(1, 4)]$）；
• 顶点 $5$ 的答案为 $-1$：从 $1$ 到 $5$ 的路径数量无限（可在路径中多次使用该自环）；
• 顶点 $6$ 的答案为 $-1$：从 $1$ 到 $6$ 的路径数量无限（可在路径中多次使用该自环）。

The first contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow. Before each test case, there is an empty line.

The first line of the test case contains two integers $n$ and $m$ ($1 \le n \le 4 \cdot 10^5, 0 \le m \le 4 \cdot 10^5$) — numbers of vertices and edges in graph respectively. The next $m$ lines contain edges descriptions. Each line contains two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$) — the start and the end of the $i$-th edge. The vertices of the graph are numbered from $1$ to $n$. The given graph can contain loops (it is possible that $a_i = b_i$), but cannot contain multi-edges (it is not possible that $a_i = a_j$ and $b_i = b_j$ for $i \ne j$).

The sum of $n$ over all test cases does not exceed $4 \cdot 10^5$. Similarly, the sum of $m$ over all test cases does not exceed $4 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示输入中测试用例的数量。随后是 $t$ 个测试用例。每个测试用例之前均有一空行。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 4 \cdot 10^5,\ 0 \le m \le 4 \cdot 10^5$）—— 分别表示图中的顶点数和边数。接下来的 $m$ 行描述各条边，每行包含两个整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$）—— 表示第 $i$ 条边的起点与终点。图中顶点编号为 $1$ 到 $n$。所给图可包含自环（即可能出现 $a_i = b_i$），但不能包含重边（即对任意 $i \ne j$，不可能同时满足 $a_i = a_j$ 且 $b_i = b_j$）。

所有测试用例的 $n$ 之和不超过 $4 \cdot 10^5$；同理，所有测试用例的 $m$ 之和也不超过 $4 \cdot 10^5$。

Output $t$ lines. The $i$-th line should contain an answer for the $i$-th test case: a sequence of $n$ integers from $-1$ to $2$.

输出 $t$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案：一个由 $n$ 个整数组成的序列，每个整数取值范围为 $-1$ 到 $2$（含端点）。