E. Посчитать секунды
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Cirno есть ориентированный ациклический граф с $$$n$$$ вершинами и $$$m$$$ ребрами. В графе ровно одна вершина, не имеющая исходящих ребер. На $$$i$$$-й вершине написано целое число $$$a_i$$$.

Каждую секунду происходит следующее:

  • Пусть $$$S$$$ — множество вершин $$$x$$$, у которых $$$a_x > 0$$$.
  • Для всех $$$x \in S$$$ из $$$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$$$. Гарантируется, что граф является ориентированным ациклическим, без кратных ребер, и ровно одна вершина не имеет исходящих ребер.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных меньше или равны $$$10\,000$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите целое число — первый момент времени, когда все $$$a_i$$$ станут $$$0$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных:

  • В момент времени $$$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$$$.