F. Революция

Имя входного файла: rebel.in
Имя выходного файла: rebel.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

В одной далекой стране правит очень мудрый и дальновидный король. Как это всегда бывает, многие люди не согласны с правлением мудрого и дальновидного короля и хотят его свергнуть. Обычно, чтобы свергнуть короля, люди объединяются в коалиции. Рассматриваемая страна не стала исключением. Всего в стране есть n различных коалиций, i-я коалиция имеет влияние в ci различных городах (при этом в любом городе может иметь влияние только одна коалиция). Внутри i-й коалиции города нумеруются от единицы до ci.

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

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

Естественно, от просьбы короля отказаться невозможно, иначе вас посчитают изменником родины и казнят.

Формат входного файла

Первая строка входного файла содержит целое число n – количество различных коалиций в стране (1 ≤ n ≤ 105).

В следующей строке входного файла перечислены n целых чисел ci – количество городов подвластных i-ой коалиции (1 ≤ ci ≤ 109).

В следующей строке входного файла содержится целое число m – количество дорог в плане первого министра (1 ≤ m ≤ 105).

В следующих m строках перечислены дороги: j-ая строка содержит четыре целых числа fj, uj, sj, vj – в j-ый год город под номером uj, принадлежащий коалиции fj, соединяется дорогой с городом под номером vj, который принадлежит коалиции sj (1 ≤ fj, sj ≤ n, 1 ≤ uj ≤ cfj, 1 ≤ vj ≤ csj).

Формат выходного файла

Если министр оказался верен своему королю, и после выполнения его плана никакие два города, принадлежащие одной коалиции, не окажутся соединены путём, то в единственной строке выходного файла выведите <<Plan is OK.>> (без кавычек). В противном же случае выведите <<Rebel after x year(s).>> (без кавычек) где x – первый год, после которого между какими-то двумя городами, принадлежащими одной и той же коалиции, будет существовать путь.

Пример:

rebel.inrebel.out
3 2 2 2 3 1 1 2 2 2 2 1 2 1 2 3 1 Rebel after 2 year(s).
3 2 2 2 3 1 1 2 2 1 2 2 1 2 2 3 1 Plan is OK.


Источник: Открытый зимний чемпионат ПетрГУ по программированию, 15 декабря 2013

Обсудить       Отправить решение



Версия для печати