eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Евакуація

Евакуація

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Одна з Надсекретних організацій, чию назву ми не маємо право розголошувати, являє собою мережу з N підземних бункерів, з'єднаних рівними за довжиною тунелями, по яким з довільного бункера можна дістатись до довільного іншого (не обов'язково напряму). Зв'язок з зовнішнім світом здійснюється через спеціальні засекречені виходи, які розміщено в деяких з бункерів.

Організації знадобилось скдасти план евакуації персоналу на випадок надзвичайної ситуації. Для цього для кожного з бункерів необхідно взнати, скільки часу потрібно для того, щоб дістатись до найближчого з виходів. Вам, як спеціалісту по таким задачам, доручено розрахувати необхідний час для кожного з бункерів за заданим описом приміщення Надсекретної організації. Для вашої ж зручності бункери пронумеровано числами від 1 до N.

Вхідні дані

Спочатку вводяться два натуральних числа N, K (1N100000, 1KN) — кількість бункерів і кількість виходів відповідно.

Далі через пропуск записано K різних чисел від 1 до N, які позначають номери бункерів, у яких розміщені виходи.

Потім йде число M (1M100000) — кількість тунелів. Далі вводиться M пар чисел – номери бункерів, з'єднаних тунелем. По кожному з тунелей можна рухатись в обидві сторони. В організації не існує тунелей, які ведуть з бункера в цей же бункер, проте може існувати більше ніж один тунель між парою бункерів.

Вихідні дані

Виведіть N чисел, відокремлених пропуском — для кожного з бункерів мінімальний час, потрібний щоб дістатись до виходу. Вважайте, що час переміщення по одному тунелю дорівнює 1.

Приклад

Вхідні дані #1
3
1
2 
3
1 2
3 1
2 3
Вихідні дані #1
1 0 1