Напишіть програму, яка реалізовуватиме пошук у ширину в орієнтованому незваженому не мульти графі без петель. Вершини графа є цілими невід'ємними числами в діапазоні від 0 до ~N–1~ (де ~N~ – кількість вершин у графі).

Граф обов'язково подавати списками суміжності. (Наприклад, як List<int>[], але чіткої вимоги щодо конкретного типу не ставиться. А вимога просто використати якийсь варіант списків суміжності ставиться; власне, інакше взагалі неясно як отримати правильний результат із прийнятними витратами часу й пам'яті.)

Вхідні дані

В першому рядку задано число ~NUM~ – кількість різних пошуків у ширину, які треба виконати (на різних графах). Далі йдуть ~NUM~ блоки, кожен з яких має таку структуру.

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

Точні обмеження на ~N~ та ~M~ свідомо не повідомляються; приблизні – ~N~ не перевищує кількадесят тисяч, ~M~ не перевищує кількасот тисяч.

Результати

Виведіть ~NUM~ рядків, у кожному з яких по ~N_i~ чисел, розділених пробілами – відстані від указаної стартової вершини орграфа до його 0-ої, 1-ої, 2-ої і т. д. вершин. Якщо деяка вершина недосяжна з указаної початкової, замість відстані виводьте число 987654321.

У попередньому абзаці сказано про ~N_i~ (а не ~N~), щоб підкреслити: кількості вершин різних графів можуть бути різними, тому різні рядки результатів можуть бути різної довжини.

Приклади

Вхід

2
3 2
0 1
1 2
1
4 4
0 1
0 3
1 2
2 3
0

Результат

987654321 0 1
0 1 2 1

Примітки

1. Переконайтеся, що Ваша програма правильно враховує, що за один запуск слід обробити кілька різних графів (зокрема, працює, коли «менший» граф йде після «більшого»).
2. У наведеному прикладі треба зробити 2 пошуки вшир: один – на орграфі з 3 вершин та 2 ребер ~0\to 1~ і ~1\to 2~, починаючи з вершини 1; інший – на орграфі з 4 вершин та 4 ребер ~0\to 1~, ~0\to 3~, ~1\to 2~ і ~2\to 3~, починаючи з вершини 0.