План бегства
시간 제한2초메모리 제한1024 MB
각 방에서 신호가 울리면 가장 가까운 K개의 출구가 번호 순으로 닫힐 때, 남은 출구 중 가장 가까운 방을 찾고 없으면 -1을 출력한다.
문제
Из офиса вашей энергетической корпорации были выкрадены чертежи инновационной электростанции. Будучи построенной, она решила бы большинство проблем современной энергетики, а вас сделала бы невероятно богатым. Не торопитесь отчаиваться: службе безопасности удалось выследить похитителя и выяснить, что сейчас чертежи хранятся в принадлежащем конкурентам подземном бункере. Лучший из ваших агентов уже отправился туда с целью выкрасть чертежи обратно, но миссия очень трудна!
Так как в системе конкурентов до сих пор присутствует уязвимость Heartbleed, ваш IT-отдел получил ограниченный доступ к системе безопасности бункера и обнаружил план помещений. Оказалось, что бункер состоит из N комнат и M соединяющих их коридоров. По каждому коридору можно ходить в обоих направлениях. Никакой коридор не соединяет комнату саму с собой, никакая пара комнат не соединена более чем одним коридором (действительно, кому может прийти в голову организовать коридоры иначе?).
В некоторых комнатах расположены выходы из бункера. Как только ваш агент возьмёт чертежи, в комнате, где он находится, сработает сигнализация. После этого все выходы закроются, и агент окажется в ловушке.
Закалённая участием в CTF, ваша IT-команда смогла изменить настройки системы безопасности таким образом, что при срабатывании в комнате i сигнализации закроются не все выходы из бункера, а только K ближайших к данной комнате. Расстояние между двумя комнатами определяется как минимальное количество коридоров, по которым надо пройти, чтобы добраться из одной комнаты в другую. Расположенные на одинаковом расстоянии от комнаты i выходы система будет закрывать в порядке возрастания номеров содержащих их комнат.
Когда сработает сигнализация и поднимется тревога, агенту необходимо как можно быстрее покинуть бункер. Поскольку расположение чертежей заранее неизвестно, то необходимо для каждой комнаты бункера вычислить, где будет расположен ближайший незапертый выход, если в этой комнате сработает сигнализация. Из незапертых выходов на одинаковом расстоянии от данной комнаты следует определить выход, расположенный в комнате с наименьшим номером.
입력
В первой строке ввода записаны через пробел два целых числа N и M, обозначающие количество комнат и коридоров в бункере (1 ⩽ N ⩽ 100 000, 0 ⩽ M ⩽ 100 000).
Следующие M строк содержат по два числа ai и bi — номера комнат, соединенных i-м коридором (1 ⩽ ai, bi ⩽ N).
Далее следует число A — количество комнат с выходами из бункера (1 ⩽ A ⩽ N).
В следующей строке содержатся A разделённых пробелами различных чисел ei, обозначающих номера комнат, в которых расположены выходы (1 ⩽ ei ⩽ N).
В последней строке ввода содержится целое число K (0 ⩽ K ⩽ 10) — количество выходов, закрывающихся при срабатывании сигнализации.
출력
Выведите N чисел, i-е из которых является номером ближайшей комнаты с открытым выходом после срабатывания сигнализации в комнате с номером i. Если для некоторого i подходящих комнат несколько, то выберите среди них комнату с наименьшим номером. Если же из комнаты i эвакуироваться не удастся, то выведите −1.
힌트
В первом примере K = 0, а значит необходимо просто найти ближайший выход для каждой комнаты. Ответ определяется однозначно для всех комнат, кроме 2, — выходы в комнатах 1 и 3 находятся на расстоянии одного перехода по коридору от неё, среди них требуется выбрать комнату с меньшим номером, то есть 1.
Во втором примере из комнат с номерами от 6 до 9 выбраться невозможно, так как из них достижимы только два выхода, которые оба закроются в случае срабатывания сигнализации.