题目描述

琪露诺有一个包含 $n$ 个点和 $m$ 条边的有向无环图（DAG）。该图恰好有一个没有出边的节点。第 $i$ 个节点上有一个整数 $a_i$。

每一秒会发生如下操作：

• 设 $S$ 为所有满足 $a_x > 0$ 的节点 $x$ 的集合。
• 对于所有 $x \in S$，将 $a_x$ 减去 $1$，然后对于每一个存在从 $x$ 到 $y$ 的边的节点 $y$，将 $a_y$ 加上 $1$。

请你求出所有 $a_i$ 都变为 $0$ 的最早时刻。由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$，表示图中点和边的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个节点上的整数。

接下来的 $m$ 行，每行包含两个整数 $x, y$，表示一条从 $x$ 到 $y$ 的有向边。保证图是一个无环图，没有重边，且恰好有一个节点没有出边。

输出格式

对于每个测试用例，输出一个整数，表示所有 $a_i$ 都变为 $0$ 的最早时刻，对 $998\,244\,353$ 取模。

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

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]$。

所以答案是 $5$。

在第三个测试用例中：

所有 $a_i$ 都变为 $0$ 的最早时刻是 $6\cdot 998244353 + 4$。

由 ChatGPT 4.1 翻译

1
2 1
0 0
1 2

0

1
3 2
1 1 1
1 2
2 3

3

数据范围

保证所有测试用例中 $n$ 的和与 $m$ 的和都不超过 $10\,000$。

（$1 \leq t \leq 1000$）

（$1 \leq n, m \leq 1000$）

（$0 \leq a_i \leq 10^9$）

（$1 \leq x, y \leq n$）