eolymp
Competitions

2011 Зимняя Школа, Харьков, День 8, День Виталия Гольдштейна

Почтальон

В городе есть n площадей, соединенных улицами. При этом количество улиц не превышает ста тысяч и существует не более трех площадей, на которые выходит нечетное число улиц. Для каждой улицы известна ее длина. По улицам разрешено движение в обе стороны. В городе есть хотя бы одна улица. От любой площади до любой можно дойти по улицам.

Почтальону требуется пройти хотя бы один раз по каждой улице так, чтобы длина его пути была наименьшей. Он может начать движение на любой площади и закончить также на любой (в том числе и на начальной).

Входные данные

Первая строка входного файла содержит натуральное число n — количество площадей в городе (1n1000). Далее следуют n строк, задающих улицы. В i-ой из этих строк находится число mi — количество улиц, выходящих из площади i. Далее следуют mi пар положительных чисел. В j-ой паре первое число — номер площади, в которую идет j-ая улица с i-ой площади, а второе число — длина этой улицы.

Между двумя площадями может быть несколько улиц, но не может быть улиц с площади на нее саму.

Все числа во входном файле не превосходят 105.

Выходные данные

Если решение существует, то в первую строку выходного файла выведите одно число — количество улиц в искомом маршруте (считая первую и последнюю), а во вторую — номера площадей в порядке их посещения.

Если решений нет, выведите в выходной файл одно число -1.

Если решений несколько, выведите любое.

Time limit 2 seconds
Memory limit 256 MiB
Input example #1
4
2 2 1 2 2
4 1 2 4 4 3 5 1 1
2 2 5 4 8
2 3 8 2 4
Output example #1
5
1 2 4 3 2 1
Author Vitaly Goldstein
Source Winter School, Kharkov, 2011, Day 9