Jamping monkey
Вы охотник, преследующий обезьяну в лесу, и пытаетесь сбить её своим мощным автоматическим пулемётом. Обезьяна скрывается за ветвями одного из деревьев, вне вашего поля зрения. Вы можете прицелиться в одно из деревьев и выстрелить; ваши пули пробивают ветви и мгновенно убивают обезьяну, если она находится на этом дереве. Если её там нет, обезьяна воспользуется временем, которое вам нужно на перезарядку, и перепрыгнет на соседнее дерево, оставаясь незамеченной. Она никогда не остаётся на одном месте после выстрела. Ваша задача — выяснить, существует ли стратегия, которая позволит вам поймать обезьяну наверняка, независимо от её начального местоположения и последующих прыжков. Если такая стратегия существует, вам нужно определить кратчайшую последовательность выстрелов, которая это гарантирует.
Рисунок 2
Рассмотрим пример, когда в лесу есть только два соседних дерева (левая сторона Рисунка 2). В этом случае можно гарантировать поимку обезьяны, дважды выстрелив в одно и то же дерево. Ваш первый выстрел будет успешным, если обезьяна изначально находилась там. В противном случае обезьяна была за другим деревом и обязательно переместится, когда вы выстрелите во второй раз.
Однако, в зависимости от структуры леса, может оказаться, что вы не сможете гарантировать победу. Например, если есть три дерева, все соединённые друг с другом (правая сторона Рисунка 2). Независимо от того, куда вы целитесь, всегда есть два возможных местоположения для обезьяны в любой момент времени. (Заметьте, что здесь мы рассматриваем наихудший сценарий, когда обезьяна может постоянно угадывать ваше следующее целевое дерево).
Входные данные
Входные данные состоят из нескольких тестов, разделённых одной пустой строкой. Каждый тест начинается с строки, содержащей два целых числа n и m (1 ≤ n ≤ 21); n — это количество деревьев в лесу, а m — количество связей между деревьями. Каждая из следующих m строк содержит два различных целых числа от 0 до n-1 (включительно), идентификаторы деревьев в соседней паре. Порядок деревьев в паре не имеет значения, и ни одна пара не появляется более одного раза. Вы также можете предположить, что ни одно дерево не соседствует с самим собой, и всегда существует путь между любыми двумя деревьями в лесу.
Тесты заканчиваются строкой, содержащей только два нуля (также предшествующей пустой строкой).
Выходные данные
Выведите строку для каждого теста. Строка должна содержать единственное слово 'Impossible', если задача невыполнима. В противном случае она должна содержать кратчайшую последовательность выстрелов с требуемым свойством в формате L: V_1V_2...V_L, где L — длина последовательности, а V_1, V_2,..., V_L — это разделённые пробелами целые числа, содержащие идентификаторы деревьев, в которые нужно стрелять в правильном порядке. Если существует несколько кратчайших последовательностей, выведите лексикографически наименьшую. (Последовательность меньше другой в лексикографическом порядке, если первый элемент, по которому они различаются, меньше в первой).