Задача №114153. План бегства
Из офиса вашей энергетической корпорации были выкрадены чертежи инновационной электростанции. Будучи построенной, она решила бы большинство проблем современной энергетики, а вас сделала бы невероятно богатым. Не торопитесь отчаиваться: службе безопасности удалось выследить похитителя и выяснить, что сейчас чертежи хранятся в принадлежащем конкурентам подземном бункере. Лучший из ваших агентов уже отправился туда с целью выкрасть чертежи обратно, но миссия очень трудна!
Так как в системе конкурентов до сих пор присутствует уязвимость Heartbleed, ваш IT-отдел получил ограниченный доступ к системе безопасности бункера и обнаружил план помещений. Оказалось, что бункер состоит из N комнат и M соединяющих их коридоров. По каждому коридору можно ходить в обоих направлениях. Никакой коридор не соединяет комнату саму с собой, никакая пара комнат не соединена более чем одним коридором (действительно, кому может прийти в голову организовать коридоры иначе?).
В некоторых комнатах расположены выходы из бункера. Как только ваш агент возьмёт чертежи, в комнате, где он находится, сработает сигнализация. После этого все выходы закроются, и агент окажется в ловушке. Закалённая участием в CTF, ваша IT-команда смогла изменить настройки системы безопасности таким образом, что при срабатывании в комнате i сигнализации закроются не все выходы из бункера, а только K ближайших к данной комнате. Расстояние между двумя комнатами определяется как минимальное количество коридоров, по которым надо пройти, чтобы добраться из одной комнаты в другую. Расположенные на одинаковом расстоянии от комнаты i выходы система будет закрывать в порядке возрастания номеров содержащих их комнат.
Когда сработает сигнализация и поднимется тревога, агенту необходимо как можно быстрее покинуть бункер. Поскольку расположение чертежей заранее неизвестно, то необходимо для каждой комнаты бункера вычислить, где будет расположен ближайший незапертый выход, если в этой комнате сработает сигнализация. Из незапертых выходов на одинаковом расстоянии от данной комнаты следует определить выход, расположенный в комнате с наименьшим номером.
В первой строке ввода записаны через пробел два целых числа N и M , обозначающие количество комнат и коридоров в бункере ( 1 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000 ).
Следующие M строк содержат по два числа a i и b i — номера комнат, соединенных i -м коридором ( 1 ≤ a i , b i ≤ N ).
Далее следует число A — количество комнат с выходами из бункера ( 1 ≤ A ≤ N ).
В следующей строке содержатся A разделённых пробелами различных чисел e i , обозначающих номера комнат, в которых расположены выходы ( 1 ≤ e i ≤ N ).
В последней строке ввода содержится целое число K ( 0 ≤ K ≤ 10 ) — количество выходов, закрывающихся при срабатывании сигнализации.
Выведите N чисел, i -е из которых является номером ближайшей комнаты с открытым выходом после срабатывания сигнализации в комнате с номером i . Если для некоторого i подходящих комнат несколько, то выберите среди них комнату с наименьшим номером. Если же из комнаты i эвакуироваться не удастся, то выведите - 1 .
В первом примере K = 0 , а значит необходимо просто найти ближайший выход для каждой комнаты. Ответ определяется однозначно для всех комнат, кроме 2 , — выходы в комнатах 1 и 3 находятся на расстоянии одного перехода по коридору от неё, среди них требуется выбрать комнату с меньшим номером, то есть 1 .
Во втором примере из комнат с номерами от 6 до 9 выбраться невозможно, так как из них достижимы только два выхода, которые оба закроются в случае срабатывания сигнализации.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп , в том числе тестов из условия .
5 5 1 2 2 3 3 4 4 5 5 1 2 1 3 0
1 1 3 3 1
9 10 1 2 2 3 3 4 4 5 6 7 6 8 6 9 7 8 7 9 8 9 7 1 2 3 4 5 6 7 2
3 3 4 5 3 -1 -1 -1 -1