Count Seconds

题意翻译

Cirno 有一个有向无环图，该图有 $n$ 个点和 $m$ 条边，其中有且仅有一个点没有出边。对于所有 $i\in[1,n]$，第 $i$ 个点有一个整数 $a_i$。 每秒钟都会发生以下事件： + 令点集 $S=\{x|a_x>0\}$ 。 + 对于每个点 $x\in S$，$a_x$ 都会自减 $1$，然后对于每个与 $x$ 连着有向边 $x\rightarrow y$ 的点 $y$，$a_y$ 自增 $1$。 请求出所有的 $a_i$ 都变成 $0$ 的最早时刻，在模 $998\ 244\ 353$ 的意义下。

题目描述

Cirno has a DAG (Directed Acyclic Graph) with $ n $ nodes and $ m $ edges. The graph has exactly one node that has no out edges. The $ i $ -th node has an integer $ a_i $ on it. Every second the following happens: - Let $ S $ be the set of nodes $ x $ that have $ a_x > 0 $ . - For all $ x \in S $ , $ 1 $ is subtracted from $ a_x $ , and then for each node $ y $ , such that there is an edge from $ x $ to $ y $ , $ 1 $ is added to $ a_y $ . Find the first moment of time when all $ a_i $ become $ 0 $ . Since the answer can be very large, output it modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. Description of test cases follows. The first line of each test case contains two integers $ n, m $ ( $ 1 \leq n, m \leq 1000 $ ) — the number of vertices and edges in the graph. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ) — the integer on vertices. Each line of the following $ m $ lines contains two integers $ x, y $ ( $ 1 \leq x, y \leq n $ ), represent a directed edge from $ x $ to $ y $ . It is guaranteed that the graph is a DAG with no multi-edges, and there is exactly one node that has no out edges. It is guaranteed that both sum of $ n $ and sum of $ m $ over all test cases are less than or equal to $ 10\,000 $ .

输出格式

For each test case, print an integer in a separate line — the first moment of time when all $ a_i $ become $ 0 $ , modulo $ 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

说明

In the first test case: - At time $ 0 $ , the values of the nodes are $ [1, 1, 1] $ . - At time $ 1 $ , the values of the nodes are $ [0, 1, 1] $ . - At time $ 2 $ , the values of the nodes are $ [0, 0, 1] $ . - At time $ 3 $ , the values of the nodes are $ [0, 0, 0] $ . So the answer is $ 3 $ . In the second test case: - At time $ 0 $ , the values of the nodes are $ [1, 0, 0, 0, 0] $ . - At time $ 1 $ , the values of the nodes are $ [0, 1, 0, 0, 1] $ . - At time $ 2 $ , the values of the nodes are $ [0, 0, 1, 0, 0] $ . - At time $ 3 $ , the values of the nodes are $ [0, 0, 0, 1, 0] $ . - At time $ 4 $ , the values of the nodes are $ [0, 0, 0, 0, 1] $ . - At time $ 5 $ , the values of the nodes are $ [0, 0, 0, 0, 0] $ . So the answer is $ 5 $ .In the third test case: The first moment of time when all $ a_i $ become $ 0 $ is $ 6\cdot 998244353 + 4 $ .

题目大意：
Cirno有一个有向无环图（DAG），该图有n个节点和m条边，其中一个节点没有出边。每个节点上有一个整数a_i。每秒钟，对于所有a_x>0的节点x，a_x自减1，然后对于每个与x连着有向边x→y的节点y，a_y自增1。求所有a_i都变成0的最早时刻，结果对998244353取模。

输入输出数据格式：
输入格式：
- 第一行一个整数t（1≤t≤1000），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n, m（1≤n, m≤1000），分别表示图中的节点数和边数。
- 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i≤10^9），表示节点上的整数。
- 接下来的m行，每行包含两个整数x, y（1≤x, y≤n），表示从x到y的一条有向边。保证图是一个没有重边的DAG，并且恰好有一个节点没有出边。
- 保证所有测试用例的n和m之和都不超过10000。

输出格式：
- 对于每个测试用例，输出一行一个整数，表示所有a_i都变成0的最早时刻，结果对998244353取模。

输入输出样例：
输入样例 #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
```题目大意： Cirno有一个有向无环图（DAG），该图有n个节点和m条边，其中一个节点没有出边。每个节点上有一个整数a_i。每秒钟，对于所有a_x>0的节点x，a_x自减1，然后对于每个与x连着有向边x→y的节点y，a_y自增1。求所有a_i都变成0的最早时刻，结果对998244353取模。 输入输出数据格式： 输入格式： - 第一行一个整数t（1≤t≤1000），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n, m（1≤n, m≤1000），分别表示图中的节点数和边数。 - 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i≤10^9），表示节点上的整数。 - 接下来的m行，每行包含两个整数x, y（1≤x, y≤n），表示从x到y的一条有向边。保证图是一个没有重边的DAG，并且恰好有一个节点没有出边。 - 保证所有测试用例的n和m之和都不超过10000。 输出格式： - 对于每个测试用例，输出一行一个整数，表示所有a_i都变成0的最早时刻，结果对998244353取模。 输入输出样例： 输入样例 #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 ```