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

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

Формат вхідних даних

Спочатку вводяться два натуральні числа \(𝑁 , 𝐾\) (\(1 ≤ 𝑁 ≤ 100000\), \(1 ≤ 𝐾 ≤ 𝑁\) ) — кількість бункерів і кількість виходів відповідно.

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

Потім йде число \(𝑀\) (\(1 ≤ 𝑀 ≤ 100 000\)) - кількість тунелів.

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

Формат вихідних даних

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

Приклад вхідних даних

3
1
2 
3
1 2
3 1
2 3

Приклад вихідних даних

1 0 1

Приклад вхідних даних

10
2
10 8 
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2

Приклад вихідних даних

1 4 1 2 1 3 2 0 3 0