Листоноша
У місті є n площ, з'єднаних вулицями. При цьому кількість вулиць не перевищує ста тисяч і існує не більше трьох площ, на які виходить непарне число вулиць. Для кожної вулиці відома її довжина. По вулицям дозволено рух в обидві сторони. У місті є хоча б одна вулиця. Від довільної площі до довільної можна дійти по вулицям.
Листоноші потрібно пройти хоча б один раз по кожній вулиці так, щоб довжина його шляху була найменшою. Він може почати рух на довільній площі і завершити також на довільній (у тому числі і на початковій).
Вхідні дані
Перший рядок вхідного файлу містить натуральне число n — кількість площ у місті (1 ≤ n ≤ 1000). Далі йде n рядків, які задають вулиці. У i-му з цих рядків знаходиться число m_i — кількість вулиць, які виходять з площі i. Далі йде m_i пар додатніх чисел. У j-ій парі перше число — номер площі, на яку йде j-та вулиця з i-ої площі, а друге число — довжина цієї вулиці.
Між двома площами може бути декілька вулиць, але не може бути вулиць з площі на неї саму.
Усі числа у вхідному файлі не перевищують 10^5.
Вихідні дані
Якщо розв'язок існує, то у перший рядок вихідного файлу виведіть одне число — кількість вулиць у шуканому маршруті (рахуючи першу і останню), а у другий — номери площ у порядку їх відвідування.
Якщо розв'язків немає, виведіть у вихідний файл одне число -1.
Якщо розв'язків декілька, виведіть довільний.