План бегства

문제

Из офиса вашей энергетической корпорации были выкрадены чертежи инновационной электростанции. Будучи построенной, она решила бы большинство проблем современной энергетики, а вас сделала бы невероятно богатым. Не торопитесь отчаиваться: службе безопасности удалось выследить похитителя и выяснить, что сейчас чертежи хранятся в принадлежащем конкурентам подземном бункере. Лучший из ваших агентов уже отправился туда с целью выкрасть чертежи обратно, но миссия очень трудна!

Так как в системе конкурентов до сих пор присутствует уязвимость 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