← 返回题目列表

Codeforces · 1547/G

G. 有多少条路径?

中文机器翻译题面 查看原题

给你一个有向图$$$G$$$,它可以包含循环(从顶点到自身的边)。 $$$G$$$ 中不存在多重边,这意味着对于所有有序对 $$$(u, v)$$$ 至多存在从 $$$u$$$ 到 $$$v$$$ 的一条边。顶点编号从 $$$1$$$ 到 $$$n$$$。

从 $$$u$$$ 到 $$$v$$$ 的路径是一系列边,使得:

- 顶点 $$$u$$$ 是路径中第一条边的起点;
- 顶点 $$$v$$$ 是路径中最后一条边的末端;
- 对于所有相邻边对,下一条边从前一条边结束的顶点开始。

我们假设空的边序列是从 $$$u$$$ 到 $$$u$$$ 的路径。

对于每个顶点 $$$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$$$ 的路径数量是无限的(循环可以在路径中使用多次)。

输入

第一个包含一个整数 $$$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$$$。

输出

输出 $$$t$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 测试用例的答案:从 $$$-1$$$ 到 $$$2$$$ 的 $$$n$$$ 整数序列。

示例

输入 #1

5

6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6

1 0

3 3
1 2
2 3
3 1

5 0

4 4
1 2
2 3
1 4
4 3

输出 #1

1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1