← 返回题目列表

Codeforces · 1704/E

E. 计数秒

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

Cirno 有一个 DAG(有向无环图),具有 $$$n$$$ 节点和 $$$m$$$ 边。该图恰好有一个没有出边的节点。第 $$$i$$$ 个节点上有一个整数 $$$a_i$$$。

每秒都会发生以下情况:

- 设 $$$S$$$ 为 $$$x$$$ 且 $$$a_x > 0$$$ 的节点集。
- 对于S$$$中的所有$$$x,从$$$a_x$$$中减去$$$1$$$,然后对于每个节点$$$y$$$,使得存在从$$$x$$$到$$$y$$$的边,将$$$1$$$添加到$$$a_y$$$。

找到所有 $$$a_i$$$ 变为 $$$0$$$ 的第一个时刻。由于答案可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$) — 图中顶点和边的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 顶点上的整数。

以下 $$$m$$$ 行中的每一行包含两个整数 $$$x, y$$$ ($$$1 \leq x, y \leq n$$$),表示从 $$$x$$$ 到 $$$y$$$ 的有向边。保证图是一个没有多边的DAG,并且恰好有一个节点没有出边。

保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和小于或等于 $$$10\,000$$$。

输出

对于每个测试用例,在单独的行中打印一个整数 - 所有 $$$a_i$$$ 变为 $$$0$$$ 的第一个时刻,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

5
3 2
1 1 1
1 2
2 3
5 5
1 0 0 0 0
1 2
2 3
3 4
4 5
1 5
10 11
998244353 0 0 0 998244353 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 3
7 9
5 6
1293 1145 9961 9961 1919
1 2
2 3
3 4
5 4
1 4
2 4
6 9
10 10 10 10 10 10
1 2
1 3
2 3
4 3
6 3
3 5
6 5
6 1
6 2

输出 #1

3
5
4
28010
110

注意

在第一个测试用例中:

- 在时间$$$0$$$,节点的值为$$$[1, 1, 1]$$$。
- 在时间$$$1$$$,节点的值为$$$[0, 1, 1]$$$。
- 在时间$$$2$$$,节点的值为$$$[0, 0, 1]$$$。
- 在时间$$$3$$$,节点的值为$$$[0, 0, 0]$$$。

所以答案是$$$3$$$。

- 在时间$$$0$$$,节点的值为$$$[1, 0, 0, 0, 0]$$$。
- 在时间$$$1$$$,节点的值为$$$[0, 1, 0, 0, 1]$$$。
- 在时间$$$2$$$,节点的值为$$$[0, 0, 1, 0, 0]$$$。
- 在时间$$$3$$$,节点的值为$$$[0, 0, 0, 1, 0]$$$。
- 在时间 $$$4$$$ 时,节点的值为 $$$[0, 0, 0, 0, 1]$$$。
- 在时间$$$5$$$,节点的值为$$$[0, 0, 0, 0, 0]$$$。

在第三个测试用例中:

所有$$$a_i$$$变为$$$0$$$的第一个时刻是$$$6\cdot 998244353 + 4$$$。