eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Листоноша

Листоноша

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

У місті є n площ, з'єднаних вулицями. При цьому кількість вулиць не перевищує ста тисяч і існує не більше трьох площ, на які виходить непарне число вулиць. Для кожної вулиці відома її довжина. По вулицям дозволено рух в обидві сторони. У місті є хоча б одна вулиця. Від довільної площі до довільної можна дійти по вулицям.

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

Вхідні дані

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

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

Усі числа у вхідному файлі не перевищують 10^5.

Вихідні дані

Якщо розв'язок існує, то у перший рядок вихідного файлу виведіть одне число — кількість вулиць у шуканому маршруті (рахуючи першу і останню), а у другий — номери площ у порядку їх відвідування.

Якщо розв'язків немає, виведіть у вихідний файл одне число -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
Вихідні дані #1
5
1 2 4 3 2 1
Автор Віталій Гольдштейн
Джерело Зимова Школа, Харків 2011, День 9