Пошук зачарованого предмета#1824
Ви — шукач, який розшукує захований предмет у зачарованому лісі. Предмет схований за гілками одного з дерев, поза вашим полем зору. Ви можете перевірити («обшукати») будь-яке з дерев; якщо предмет знаходиться в цьому дереві, ви знаходите його миттєво. Якщо ж ні, предмет переміщується, переходячи по з'єднаннях до сусіднього дерева, поки ви зайняті пошуком, і ви про це не здогадуєтесь. Після кожного пошуку предмет ніколи не залишається на тому самому місці. Ви бажаєте визначити, чи існує стратегія пошуку, яка гарантує знаходження предмета незалежно від його початкової позиції та наступних переміщень. Якщо така стратегія існує, ви повинні знайти найкоротшу послідовність обшуків, яка гарантує успіх.
Рисунок 2
Наприклад, розглянемо випадок, коли в лісі з'єднано лише два дерева (ліва частина рисунка 2). Тоді можна гарантувати знаходження предмета, двічі обшукавши одне й те саме дерево. Якщо предмет буде там під час першого пошуку, ви його знайдете. Якщо ж ні, він мусив бути в іншому дереві і переміститься під час другого пошуку, що гарантує вам знаходження предмета тоді.
Однак, залежно від структури лісу, може виявитися, що ви не здатні гарантувати успіх. Один із таких випадків — якщо є три дерева, кожне з яких з'єднане з кожним (права частина рисунка 2). Без різниці, де ви шукаєте, завжди залишається два можливих місця знаходження предмета в будь-який момент. (Зверніть увагу, що вам слід планувати найгірший сценарій, коли предмет завжди передбачає, де ви будете шукати наступного разу.)
Вхід містить кілька тестових випадків, кожен з яких відокремлений одним порожнім рядком. Кожен тестовий випадок починається з рядка з двома цілими числами та (1 \leq n \leq 21); — кількість дерев у лісі, — кількість зв'язків між деревами. Кожен із наступних рядків містить по два різних цілих числа від до n-1 (включно), які ідентифікують сусідні дерева. Порядок дерев у парі не має значення, і жодна пара не зустрічається більше одного разу. Крім того, жодне дерево не є сусідом саме собі, і між будь-якими двома деревами лісу завжди існує шлях.
Тестові випадки завершуються рядком, що містить лише два нулі (передує йому також порожній рядок).
Для кожного тестового випадку виведіть рядок. Рядок має містити єдине слово Impossible, якщо задача неможлива. Інакше слід вивести найкоротшу послідовність потрібних обшуків у форматі : V_1 V_2 ... V_L, де — довжина послідовності, а V_1, V_2, \ldots, V_L — номери дерев, які слід обшукати в правильному порядку, розділені пробілами. Якщо існує кілька найкоротших послідовностей, виведіть лексикографічно найменшу. (Одна послідовність вважається лексикографічно меншою за іншу, якщо перший елемент, у якому вони різняться, менший у першій.)
Приклад 1