В Древнем Риме был разработан план по уничтожению варваров, но для его реализации каждый город должен быть проинформирован о нем.
Северная часть Римской Империи состоит из \(n\) городов, соединенных \(m\) односторонними дорогами. Изначально в \(i\)-м городе находится \(a_i\) гонцов, и каждый гонец может свободно перемещаться между городами по существующим дорогам. Гонец может взять с собой копию плана и информировать города, которые он посещает, а также может делать неограниченное количество копий для других гонцов в городе, в котором он находится.
В начале вы сделаете несколько копий планов и доставите их выбранным вами гонцам. Ваша цель — сделать так, что каждый город будет посещен гонцом с планом. Найдите наименьшее количество копий планов, которые вам нужно произвести изначально, чтобы гонцы доставили их в каждый город, или определите, что это невозможно сделать.
Выходные данные
Выведите одну строку, содержащую одно целое число — наименьшее количество гонцов, которым вам нужно в начале дать копию плана, или \(-1\), если невозможно проинформировать все города.
Примеры
| № | Входные данные | Выходные данные |
|
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
|