АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1968. Эвакуация

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

База одной сверхсекретной организации, чьё название мы не имеем право разглашать, представляет собой сеть из N подземных бункеров, пронумерованных от 1 до N. Некоторые пары бункеров соединены равными по длине туннелями. Также в некоторых бункерах имеются специальные засекреченные выходы, через которые осуществляется связь с внешним миром.

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

Входные данные

В первой строке записано число N, во второй – число K (1 ≤ N ≤ 100000, 1 ≤ K ≤ N) – количество бункеров и количество выходов соответственно. Далее через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы. Потом идёт целое число M (1 ≤ M ≤ 100000) – количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединённых туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

Выходные данные

Выведите N чисел, разделённых пробелом – для каждого из бункеров минимальное время, необходимое, чтобы добраться до выхода. Считайте, что время перемещения по одному любому туннелю равно 1. Если из каких-то бункеров вообще нельзя добраться до выхода (а в сверхсекретных организациях бывает и не такое), то выведите для таких бункеров -1.

Примеры

Входные данные
3
1
2
3
1 2
3 1
2 3
Выходные данные
1 0 1 
Входные данные
5
2
1 2
3
2 3
1 3
4 5
Выходные данные
0 0 1 -1 -1 

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Графы /
63. Четный граф 1968.
Учебные курсы / Алгоритмы и структуры данных / Алгоритмы на графах /
247. Удаление клеток 1968.
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Графы /
208. 02 - Михаил Густокашин против бюрократии 1968. 204. 04 - Переливания 1701. 05 - Лабиринт 292. 06 - Одностороннее движение
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2020 / Импульс-2020, графы /
792. 03 - Получи дерево 1968. 246. 05 - Путь в лабиринте 208. 06 - Михаил Густокашин против бюрократии 205. 07 - Игра в города
 
время генерации 0.25 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.