printЛето 8

printC. Дружба и кефир

Ограничения: время – 5s/10s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Любимым напитком большинства учеников K-й средней школы является кефир. Однако, в последнее время в результате активной рекламной кампании всё больше учеников переходят на новый газированный напиток "UnhealthyCola". Этот факт беспокоит школьную администрацию. В результате социологического опроса учащихся выяснилось, что у каждого школьника в классе есть ближайшие друзья, с мнением которых он считается. Если больше половины ближайших друзей школьника уже пьют UnhealthyCola, то школьник поддаётся их дурному влиянию и, в свою очередь, влияет на оставшихся друзей. К сожалению, никакое количество друзей не способно переубедить школьника перейти обратно с UnhealthyCola на кефир.
На педагогическом совете было решено, что распространение UnhealthyCola можно было бы сдержать, если бы больше школьников дружили между собой.
Требуется подружить двух учеников школы таким образом, чтобы максимизировать количество школьников, которые останутся верны кефиру.
Ввод
Входной файл содержит число школьников `N`, за которым идёт `N` чисел `c_i`, где `c_i=0`, если `i`-й ученик пьёт кефир, и `c_i=1`, если он пьёт UnhealthyCola. Далее число пар друзей `M`, за которым идут `M` пар чисел `a_i\ b_i`, означающих, что школьники `a_i` и `b_i` – друзья.
Вывод
В выходной файл должно быть выведено два числа – ученики, которых следует подружить. Если решений несколько, вывести любое из них. Если никакая пара новых друзей не улучшит результат, следует вывести число `-1`.
Ограничения
`2\ ≤\ N\ ≤\ 500`, `0\ ≤\ M\ ≤\ 1000`, `1\ ≤\ a_i,\ b_i\ ≤\ N`

Пример ввода 1

3
1 0 0
2
1 2
1 3

Пример вывода 1

2 3

Пример ввода 2

9
1 0 0 0 0 1 1 1 0
7
1 2  2 3  3 4  4 5  6 2  7 3  8 4

Пример вывода 2

9 2
Источник: А. Кленин, ДВГУ, Весенний турнир, 2005
loading