CF1704E.Count Seconds

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

Cirno 有一个包含 $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$ 取模后输出。

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

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$1 \leq n, m \leq 1000$）—— 图中顶点和边的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）—— 各顶点上的整数值。

接下来的 $m$ 行，每行包含两个整数 $x, y$（$1 \leq x, y \leq n$），表示一条从 $x$ 指向 $y$ 的有向边。保证该图是一个无重边的有向无环图（DAG），且恰好存在一个出度为 0 的节点。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $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$.

对于每个测试用例，在单独一行中输出一个整数——所有 $a_i$ 首次全部变为 $0$ 的时刻（对 $998\,244\,353$ 取模）。

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

在第一个测试用例中：

• 在时刻 $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$。