Рабочее место участника

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

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

В первой строке записано число `N\ (1\ ≤\ N\ ≤\ 1000)` – количество площадей. Далее следуют `N` строк, задающих улицы. В `i`-ой из этих строк находится число `M_i`  – количество улиц, выходящих из площади `i`, а далее следуют `M_i` пар положительных чисел. В `j`-ой паре первое число – номер площади, в которую идет `j`-ая улица с `i`-ой площади, а второе число – длина этой улицы. Между двумя площадями может быть несколько улиц, но не может быть улиц с площади на нее саму. Все числа во входном файле не превосходят `10^5`.

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

Если решений нет, выведите в выходной файл одно число –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

5
1 2 3 4 2 1