Позаземна Безпека

Ви відповідаєте за безпеку в надсекретному урядовому дослідницькому центрі. Нещодавно ваш уряд захопив живу позаземну (ET) форму життя і проводить день відкритих дверей для колег-дослідників. Звісно, не всім гостям можна довіряти, тому їм присвоєно різні рівні безпеки. Лише гості з рівнем 5 можуть бути допущені до лабораторії, де утримується позаземна форма життя; всі інші можуть вільно пересуватися по решті центру. Кожна кімната в центрі з'єднана односторонніми шлюзами, тому ви можете пройти через двері лише в одному напрямку.

Щоб захистити вашу цінну ET, ви встановите посилені заходи безпеки (у вигляді озброєних охоронців) на маршруті, що веде до кімнати, де утримується ET, але не в самій кімнаті - охоронці не мають достатнього рівня доступу, щоб увійти в кімнату з ET.

Охоронці перевірятимуть особу та рівень безпеки всіх гостей, які намагаються пройти через кімнату, в якій вони розташовані, тому ви хочете розмістити охоронців там, де вони завдадуть мінімум незручностей гостям, які не мають наміру відвідувати ET. Кімната, в якій повинні бути розміщені охоронці, повинна відповідати наступним двом умовам:

1. Щоб потрапити до кімнати з ET, гості повинні пройти через кімнату з охоронцями;

2. Немає іншої кімнати з цією властивістю, яка була б ближче до кімнати з ET - пам'ятайте, охоронці не можуть бути розміщені в самій кімнаті з ET.

Діаграма нижче ілюструє можливу карту вашого центру:

Зверніть увагу, що розміщення охоронців у кімнаті 2 задовольнило б першу умову, але кімната 3 ближче до ET, тому охоронці повинні бути розміщені в кімнаті 3.

Всі гості входять через кімнату 0, вхід до вашого центру. Ваша програма приймає послідовність рядків, що містять цілі числа. Перший рядок складається з двох цілих чисел: кількість кімнат і кімната, в якій утримується ET (звісно, з власної волі).