eolymp
bolt
Try our new interface for solving problems
Məsələlər

Автомобиль Джона

Автомобиль Джона

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Джон недавно купил новый автомобиль. Он решил показатьего всем своим друзьям, побывав на каждой улице города, в котором он живет. А для того, чтобы потратить как можно меньше бензина, он хочет проехать по каждой улице ровно один раз. Город Джона состоит из улиц и перекрестков. Каждая улица имеет уникальный номер i (1i1994). Каждый перекресток также имеет уникальный номер j (1j44). Нумерация перекрестков никак не связана с нумерацией улиц. Каждая улица соединяет ровно два перекрестка (могут существовать улицы, соединяющие перекресток с самим собой). Могут быть пары перекрестков, между которыми есть несколько улиц. Перекресток, на котором живет Джон, находится на конце первой улицы и имеет минимальный номер. Составляя план объезда всех улиц в виде последовательности номеров улиц, Джон выбрал план, соответствующий лексикографически наименьшей последовательности. Кроме того, Джон хочет вернуться в начальный перекресток.

Giriş verilənləri

Входной файл содержит несколько тестовых случаев. Каждый тестовый случай представляет собой описание города. Город описан несколькими строчками, каждая из которых описывает одну из улиц и содержит три числа: x, y и z (1x, y44, 1z1994), где x и y — номера перекрестков, соединенных улицей, а z — номер самой улицы. Каждый тестовый случай заканчивается строкой, содержащей два нуля.

Еще одна строка с двумя нулями означает конец входного файла.

Çıxış verilənləri

Для каждого тестового случая выведите блок из двух строк, содержащий ответ. В первой строке должна быть последовательность номеров улиц в порядке посещения улиц Джоном. Вторая строка должна быть пустой. Если у описанного города не существует ни одного требуемого объезда, то выведите без кавычек фразу "Round trip does not exist.".

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
1 2 3 5 4 6

Round trip does not exist.

Mənbə ЛКШ-2011 Севастополь 08.08.2011 д.1 1-я лига