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