В городе есть N площадей, соединенных улицами. При этом количество улиц не превышает 100000 и существует не более трех площадей, на которые выходит нечетное количество улиц. Для каждой улицы известна ее длина. По каждой улице разрешено движение в обе стороны. В городе есть хотя бы одна улица. От каждой площади до любой другой можно дойти по улицам.
Почтальону требуется пройти хотя бы один раз по каждой улице. Почтальон хочет, чтобы длина его пути была минимальна. Он может начать движение на любой площади и закончить также на любой (в том числе и на начальной).
Помогите почтальону составить такой маршрут.
Входные данные
Сначала записано число N — количество площадей в городе (2≤N≤1000). Далее следуют N строк, задающих улицы. В i-ой из этих строк находится число mi — количество улиц, выходящих из площади i. Далее следуют mi
пар натуральных чисел: в j-ой паре первое число — номер площади, в которую идет j-ая улица с i
-ой площади, а второе число — длина этой улицы.
Между двумя площадями может быть несколько улиц, но не может быть улицы с площади на нее саму.
Все числа во входном файле не превосходят 100000
Выходные данные
Если решение существует, то в первую строку выходного файла выведите одно число — количество улиц в искомом маршруте, а во вторую — номера площадей в порядке их посещения.
Если решения нет, выведите в выходной файл одно число –1.
Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
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
|