Задачі
Автомобиль Джона
Автомобиль Джона
Джон недавно купил новый автомобиль. Он решил показатьего всем своим друзьям, побывав на каждой улице города, в котором он живет. А для того, чтобы потратить как можно меньше бензина, он хочет проехать по каждой улице ровно один раз. Город Джона состоит из улиц и перекрестков. Каждая улица имеет уникальный номер \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{1994}). Каждый перекресток также имеет уникальный номер \textbf{j} (\textbf{1} ≤ \textbf{j} ≤ \textbf{44}). Нумерация перекрестков никак не связана с нумерацией улиц. Каждая улица соединяет ровно два перекрестка (могут существовать улицы, соединяющие перекресток с самим собой). Могут быть пары перекрестков, между которыми есть несколько улиц. Перекресток, на котором живет Джон, находится на конце первой улицы и имеет минимальный номер. Составляя план объезда всех улиц в виде последовательности номеров улиц, Джон выбрал план, соответствующий лексикографически наименьшей последовательности. Кроме того, Джон хочет вернуться в начальный перекресток.
\InputFile
Входной файл содержит несколько тестовых случаев. Каждый тестовый случай представляет собой описание города. Город описан несколькими строчками, каждая из которых описывает одну из улиц и содержит три числа: \textbf{x}, \textbf{y} и \textbf{z} (\textbf{1} ≤ \textbf{x}, \textbf{y} ≤ \textbf{44}, \textbf{1} ≤ \textbf{z} ≤ \textbf{1994}), где \textbf{x} и \textbf{y} --- номера перекрестков, соединенных улицей, а \textbf{z} --- номер самой улицы. Каждый тестовый случай заканчивается строкой, содержащей два нуля.
Еще одна строка с двумя нулями означает конец входного файла.
\OutputFile
Для каждого тестового случая выведите блок из двух строк, содержащий ответ. В первой строке должна быть последовательность номеров улиц в порядке посещения улиц Джоном. Вторая строка должна быть пустой. Если у описанного города не существует ни одного требуемого объезда, то выведите без кавычек фразу "\textbf{Round trip does not exist.}".
Вхідні дані #1
1 2 1 2 3 2 3 1 6 1 2 5 2 3 3 3 1 4 0 0 1 2 1 2 3 2 1 3 3 2 4 4 0 0 0 0
Вихідні дані #1
1 2 3 5 4 6 Round trip does not exist.