Напишіть програму, яка реалізовуватиме пошук у ширину в простому графі, вершини якого не нумеровані й ідентифікуються словесними назвами.

Вхідні дані

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

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

Результати

Виведіть на стандартний вихід (екран) NUM блоків, у кожному з яких записані відстані від вказаної початкової вершини до всіх досяжних (якщо є недосяжні вершини, вони взагалі не згадуються). Перелік повинен бути відсортований за назвами вершин, кожна пара (назва, відстань) повинна виводитися в окремому рядку, блоки мають бути відділені один від одного рядком === (три знаки «дорівнює»).

Приклади

Вхід

2
2
Cherk Zol
Cherk Sm
Zol
4
A Bb
Bb Ccc
Ccc A
Dddd Eeeee
Bb

Результат

Cherk 1
Sm 2
Zol 0
===
A 1
Bb 0
Ccc 1

Примітки

Задачу можна розв'язати, наприклад, будь-яким з таких двох способів (можливі й інші, це лише приклади правильних):

• Граф подавати так само, як у задачі «Пошук у ширину — 1», а для перетворень назв у номери та номерів у назви користуватися SortedDictionary<string, int> та List<string> відповідно. Для виведення у відсортованому порядку використати той самий SortedDictionary<string, int>, що перетворює назви у номери.
• Увесь час працювати безпосередньо з рядковими назвами, подаючи граф, наприклад, як Dictionary<string, List<string> >. Відповідно замінюються й решта структур даних. Зокрема, масив відстаней перетворюється у, наприклад, SortedDictionary<string, int>, який міститиме по суті готову відповідь конкретного пошуку.