eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Денежные дела

Денежные дела

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Наш грустный рассказ начинается с кучки бывалых друзей. Вместе они отправились в путешествие в живописную страну Молванию. Там с ними произошли различные события, о которых слишком ужасно здесь упоминать. Конечным результатом было то, что в последний вечер путешественники обменялись между собой фразой "Я никогда не хочу Вас видеть снова!". Быстрый подсчет показал, что возможно, это было сказано почти 50 миллионов раз!

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

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

Вхідні дані

Первая строка содержит два числа n (2n10000) и m (0m50000) - количество друзей и число оставшихся пар дружеских отношений. Далее следует n строк, каждая из которых содержит сумму o (-10000o10000), которую каждый из друзей задолжал (или ему причитается, если o < 0). Сумма всех этих чисел равна нулю. Далее следуют m строк, каждая из которых содержит два числа x,y (0x < yn- 1) указывающих на то что x и y все еще являются друзьями.

Вихідні дані

Вывести строку "POSSIBLE" или "IMPOSSIBLE".

Приклад

Вхідні дані #1
5 3
100
-75
-25
-42
42
0 1
1 2
3 4
Вихідні дані #1
POSSIBLE
Джерело 2009 Nordic Collegiate Programming Contest, Октябрь 3, Задача B