Count Seconds
Contest: CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2200
Tags: brute force, constructive algorithms, dp, graphs, implementation, math

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$$$.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

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

In the third test case:

The first moment of time when all $$$a_i$$$ become $$$0$$$ is $$$6\cdot 998244353 + 4$$$.

Example input:
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

Example output:
3
5
4
28010
110

Editorial:
For the sink point, We can find that it may be zero at some time $$$t$$$ and $$$t \leq n$$$, then it will be full for some continous time, and then will be zero forever. That's because for time $$$t\ge n$$$, for some certain $$$a_x>0$$$, all roads from $$$x$$$ to the sink point must be greater than $$$0$$$ since $$$n$$$ rounds are enough for such $$$a_x$$$ to spread along these roads. Meanwhile, when some $$$a_y$$$ is decreased, it will also receive the numbers from upper nodes $$$x$$$. As a result, after $$$n$$$ turns, $$$a_y$$$ will be greater than $$$0$$$ until all $$$a_x$$$ turns to $$$0$$$ for all $$$x$$$ that there's an edge from $$$x$$$ to $$$y$$$.
Simulate the first $$$n$$$ rounds, then we just need to calculate what's the final number on the sink node if the the number on the sink point is never decreased. That's exactly the rounds it will take the sink point to be decreased to $$$0$$$.
Let $$$dp_i$$$ be the total number of $$$1$$$s the i-th node will add to some sink point finally if there is an $$$1$$$ on the i-th node. We can easily get the $$$dp_i$$$ in O(n) time for every sink point.
Do a topological sort, and add the $$$sum_i$$$ of the current node $$$i$$$ to the $$$sum_j$$$ of the newly queued point $$$j$$$ during the sorting process.
Calculate the sum of $$$s_i \times dp_i$$$ and you can get the answer. The total time complexity will be $$$O(n^2)$$$.
Note that the numbers on the nodes may be a multiple of $$$998244353$$$, so pay attention to them when simulating in the first $$$n$$$ turns.