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