← 返回题目

题库练习 Count Seconds

← 上一题下一题 →

A15208 | $Count Seconds$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出