408686: GYM103262 A Цивилизация

В компьютерной игре «Цивилизация-X» каждый игрок управляет империей, состоящей из нескольких городов. Некоторые города (как одного и того же игрока, так и разных игроков) могут быть соединены торговыми путями.

Основной задачей каждого игрока является захват городов других игроков. После того, как город захвачен, в нем начинаются беспорядки; на ликвидацию беспорядков в городе надо потратить некоторое количество золотых монет. Количество монет равно количеству городов, которые соединены с захваченным городом торговыми путями, и которые при этом принадлежат другим игрокам.

Обратите внимание, что между парой городов может быть несколько торговых путей, но все равно при расчете количества монет каждый город, соединенный с захваченным городом торговыми путями, учитывается только один раз.

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

После захвата города все торговые пути сохраняются.

Например, если игрок A захватывает город, соединенный торговыми путями с семью городами, четыре из которых принадлежат игроку A, два — игроку B и один — игроку C, то игрок A должен будет потратить три монеты на ликвидацию беспорядков. Если после этого этот же город захватит игрок B, то на ликвидацию беспорядков он должен будет потратить 5 монет.

Чтобы победить в игре, надо захватить все города, которые есть в мире.

Будем считать, что игроки не строят новые города и не создают новые торговые пути. Рассмотрим некоторую конфигурацию городов и торговых путей. Ценой победы игрока назовем минимальное количество монет, которые ему придется потратить на ликвидацию беспорядков, если он хочет победить. Определите игрока, цена победы которого минимальна.

В первой строке входных данных находятся три числа $$$N$$$, $$$M$$$ и $$$K$$$ — количество городов, торговых путей и количество игроков ($$$1\leq N, K\leq 100\,000$$$; $$$0\leq M\leq 100\,000$$$).

Во второй строке находятся $$$N$$$ чисел от 1 до $$$K$$$, $$$i$$$-е из которых равно номеру игрока, которому изначально принадлежит $$$i$$$-й город.

Далее следуют $$$M$$$ строк, каждая из которых содержит два различных числа — номера городов, соединяемых очередным торговым путем.

Города и игроки нумеруются начиная с 1. Могут быть игроки, которым изначально не принадлежит ни один город.

Выведите в выходной файл два числа — номер игрока, цена победы которого минимальна, и его цену победы. Если таких игроков несколько, выведите игрока с наименьшим номером.

Подзадача 1, 30 баллов: $$$N, M, K\leq 20$$$.

Подзадача 2, 30 баллов: $$$N, M, K \leq 1000$$$.

Подзадача 3, 30 баллов: нет городов, соединенных более чем одним торговым путем.

Подзадача 4, 10 баллов: дополнительных ограничений нет.

Кроме того, в тестах общей стоимостью 30 баллов (распределенных по разным подзадачам) будет выполняться условие $$$K=2$$$.

4 5 3
2 2 3 1
1 2
1 4
3 4
2 3
3 2

2 1