В детский сад имени Поликарпа Окунева ходят ровно $$$2n$$$ детей. Сегодня у них день игр, и дети решили устроить хоровод. Детей надо расставить по кругу в некотором порядке. Но мы имеем дело с детьми, а значит, детские капризы накладывают некоторые ограничения на этот порядок.
Все дети разбились на пары лучших друзей: в $$$i$$$-ю пару входят дети с номерами $$$2i - 1$$$ и $$$2i$$$, которые приходятся друг другу лучшими друзьями. Лучшие друзья отказываются стоять в хороводе не на соседних местах.
Известно, что $$$i$$$-й ребенок пришел на праздник в костюме $$$x_i$$$, при этом дети в одинаковых костюмах отказываются стоять в хороводе друг рядом с другом. Исключение составляют пары лучших друзей — если лучшие друзья пришли в одинаковых костюмах, они все равно будут стоять рядом, несмотря ни на что. Иными словами, если дети $$$i$$$ и $$$j$$$ — не лучшие друзья, и $$$x_i = x_j$$$, то они не могут стоять в хороводе рядом.
Воспитатели уже немного устали от организации всего мероприятия, поэтому они просят вас помочь им посчитать какое наибольшее количество детей можно поставить в хоровод, чтобы все дети в хороводе были довольны.
В первой строке дано единственное число $$$n$$$ — количество пар детей ($$$1 \leqslant n \leqslant 300\,000$$$).
В следующих $$$n$$$ строках заданы описания нарядов детей, в $$$i$$$-й строке через пробел даны два числа $$$x_{2i-1}$$$ и $$$x_{2i}$$$ — номера нарядов $$$2i-1$$$-го и $$$2i$$$-го ребенка соответственно ($$$1 \leqslant x_{2i-1}, x_{2i} \leqslant 2n$$$).
В первой строке выведите $$$k$$$ — максимальное количество пар, которые можно поставить в хоровод с данными условиями. Считайте, что даже из одной пары можно составить хоровод.
В следующей строке выведите через пробел $$$2k$$$ чисел — номера детей в порядке их следования в хороводе.
Если оптимальных ответов несколько, выведите любой.
3 1 1 1 2 1 3
2 3 4 5 6
4 1 2 3 4 4 2 1 3
4 1 2 3 4 6 5 7 8
