E. Транзитивный граф
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан ориентированный граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ ребрами.

Изначально граф $$$H$$$ совпадает с графом $$$G$$$. Затем вы решили выполнить следующие действия:

  • Если в графе $$$H$$$ существует тройка вершин $$$a$$$, $$$b$$$, $$$c$$$ такая, что есть ребро из $$$a$$$ в $$$b$$$ и ребро из $$$b$$$ в $$$c$$$, но нет ребра из $$$a$$$ в $$$c$$$, то добавить ребро из $$$a$$$ в $$$c$$$.
  • Повторять предыдущий шаг до тех пор, пока существуют такие тройки.

Заметим, что после выполнения этих действий количество ребер в $$$H$$$ может достигать $$$n^2$$$.

Вы также записали некоторые значения на вершинах графа $$$H$$$: на вершине $$$i$$$ записано значение $$$a_i$$$.

Рассмотрим простой путь, состоящий из $$$k$$$ различных вершин с номерами $$$v_1, v_2, \ldots, v_k$$$. Длина такого пути равняется $$$k$$$. Значение этого пути определим как $$$\sum_{i = 1}^k a_{v_i}$$$.

Простой путь считается самым длинным, если в графе нет другого простого пути с большей длиной.

Среди всех самых длинных простых путей в $$$H$$$ найдите тот, который имеет наименьшее значение.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — количество вершин и количество ребер.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — числа, записанные на вершинах графа $$$H$$$.

В $$$i$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — в графе $$$G$$$ есть ребро, идущее от вершины $$$v_i$$$ к вершине $$$u_i$$$. Заметим, что ребра являются ориентированными. Также заметим, что в графе могут быть петли и кратные рёбра.

Гарантируется, сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышают $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите два числа — длину самого длинного простого пути в $$$H$$$ и минимально возможное значение такого пути.

Пример
Входные данные
3
5 6
2 2 4 1 3
1 2
1 3
2 4
3 4
4 5
5 2
7 7
999999999 999999999 999999999 999999999 1000000000 999999999 1000000000
1 2
2 3
3 4
4 1
4 5
4 6
6 7
14 22
2 3 5 7 3 4 1 4 3 4 2 2 5 1
1 2
2 3
2 4
3 1
4 4
4 5
5 6
5 6
5 12
6 7
6 8
7 5
7 7
7 9
8 4
9 11
10 9
11 10
11 10
12 13
13 14
14 12
Выходные данные
5 12
6 5999999995
11 37
Примечание

В первом наборе входных данных самый длинный путь в обоих графах равен $$$1 \to 3 \to 4 \to 5 \to 2$$$. Поскольку путь включает все вершины, то минимально возможное значение самого длинного пути равно сумме значений по всем вершинам, которое равняется $$$12$$$.

Во втором наборе входных данных самый длинный путь равен $$$1 \to 2 \to 3 \to 4 \to 6 \to 7$$$. Поскольку самых длинных путей с вершиной $$$5$$$ не существует, то такой путь имеет минимально возможное значение $$$5\,999\,999\,995$$$.

В третьем наборе входных данных можно доказать, что не существует пути длиннее $$$11$$$ и что значение самого длинного пути не может быть меньше $$$37$$$. Также заметим, что данный граф содержит петли и кратные ребра.