В стране Берляндии n городов. Они пронумерованы целыми числами от 1 до n. Город номер 1 является столицей государства. Между некоторыми парами городов проложены дороги с односторонним движением, однако не все из них находятся в хорошем состоянии. Про каждую дорогу известно, нуждается ли она в ремонте. Если дорога нуждается в ремонте, то проезд по ней запрещен. Однако правительство Берляндии может отремонтировать дорогу и возобновить проезд по ней.

Сейчас над Берляндией нависла угроза войны с соседним государством, поэтому в столице было принято решение отправить в каждый город по одному военному отряду. Отряды могут передвигаться только по существующим дорогам, потому что на создание новых нет ни времени, ни средств. Однако для того, чтобы добраться до некоторых городов, возможно, придется отремонтировать какие-то дороги.

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