0368. Революция

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

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

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

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

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

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

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

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

В следующих m строках перечислены дороги: j-ая строка содержит четыре целых числа f_j, u_j, s_j, v_j – в j-ый год город под номером u_j, принадлежащий коалиции f_j, соединяется дорогой с городом под номером v_j, который принадлежит коалиции s_j (1 ≤ f_j, s_j ≤ n, 1 ≤ u_j ≤ c_fj, 1 ≤ v_j ≤ c_sj).

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

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

Пример:

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

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



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