You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

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

## Examples
```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
```
```output
3
5
4
28010
110
```

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

Now solve the problem and return the code.