Cirno 有一个 DAG(有向无环图),具有 $$$n$$$ 节点和 $$$m$$$ 边。该图恰好有一个没有出边的节点。第 $$$i$$$ 个节点上有一个整数 $$$a_i$$$。
每秒都会发生以下情况:
- 设 $$$S$$$ 为 $$$x$$$ 且 $$$a_x > 0$$$ 的节点集。
- 对于S$$$中的所有$$$x,从$$$a_x$$$中减去$$$1$$$,然后对于每个节点$$$y$$$,使得存在从$$$x$$$到$$$y$$$的边,将$$$1$$$添加到$$$a_y$$$。
找到所有 $$$a_i$$$ 变为 $$$0$$$ 的第一个时刻。由于答案可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
第一行包含一个整数 $$$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,并且恰好有一个节点没有出边。
保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和小于或等于 $$$10\,000$$$。
输出
对于每个测试用例,在单独的行中打印一个整数 - 所有 $$$a_i$$$ 变为 $$$0$$$ 的第一个时刻,以 $$$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
3 5 4 28010 110
注意
在第一个测试用例中:
- 在时间$$$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]$$$。
在第三个测试用例中:
所有$$$a_i$$$变为$$$0$$$的第一个时刻是$$$6\cdot 998244353 + 4$$$。