题目描述

Cirno 有一个有向无环图（DAG），包含 $n$ 个节点和 $m$ 条边。图中恰好有一个节点没有出边。第 $i$ 个节点上有一个整数 $a_i$。

每秒会发生以下操作：

• 设 $S$ 为所有满足 $a_x>0$ 的节点 $x$ 的集合。
• 对于所有 $x∈S$，$a_x$ 减去 $1$，然后对于每个节点 $y$，如果存在一条从 $x$ 到 $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$ 取模。

样例

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

3
5
4
28010
110

提示

样例1解释

在第一个测试用例中：

• 在时刻 $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⋅998244353+4$。