D. За императора!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Древнем Риме был разработан план по уничтожению варваров, но для его реализации каждый город должен быть проинформирован о нем.

Северная часть Римской Империи состоит из $$$n$$$ городов, соединенных $$$m$$$ односторонними дорогами. Изначально в $$$i$$$-м городе находится $$$a_i$$$ гонцов, и каждый гонец может свободно перемещаться между городами по существующим дорогам. Гонец может взять с собой копию плана и информировать города, которые он посещает, а также может делать неограниченное количество копий для других гонцов в городе, в котором он находится.

В начале вы сделаете несколько копий планов и доставите их выбранным вами гонцам. Ваша цель — сделать так, что каждый город будет посещен гонцом с планом. Найдите наименьшее количество копий планов, которые вам нужно произвести изначально, чтобы гонцы доставили их в каждый город, или определите, что это невозможно сделать.

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

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 200$$$, $$$1 \le m \le 800$$$) — количество городов и дорог.

Вторая строка содержит $$$n$$$ неотрицательных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_{i} \le n$$$) — начальное количество гонцов в каждом городе.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n, u \ne v$$$), указывая, что существует односторонняя дорога от города $$$u$$$ к городу $$$v$$$. Дороги могут повторяться.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$200$$$. Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$800$$$.

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

Выведите одну строку, содержащую одно целое число — наименьшее количество гонцов, которым вам нужно в начале дать копию плана, или $$$-1$$$, если невозможно проинформировать все города.

Пример
Входные данные
2
7 6
2 1 0 1 2 3 4
1 2
1 3
2 4
2 5
3 6
3 7
4 4
1 1 1 1
1 2
1 3
2 4
3 4
Выходные данные
2
2