Задача №114801. Хоровод разнообразия
В детский сад имени Поликарпа Окунева ходят ровно \(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