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