28513번 - Шоу фейерверков 스페셜 저지다국어

문제

На очередном осеннем фестивале планируется грандиозный фейерверк, во время которого должны запустить $n$ разноцветных ракет, каждая из которых взорвется в небе уникальным рисунком. Чтобы фейерверк получился максимально ярким, в каждую из $n$ ракет положили два заряда одинакового вида (один заряд лежит строго под другим, нельзя достать нижний, не достав сначала верхний).

Сегодня пиротехник решил проверить готовность ракет и с ужасом обнаружил, что какой-то шутник перемешал некоторые заряды местами --- теперь в некоторых ракетах находятся заряды разных видов, и при их запуске не получатся красивые узоры! Однако общий состав фейерверка не изменился --- во всех ракетах, вместе взятых, все еще по два заряда каждого из $n$ видов.

Теперь пиротехника ждет бессонная ночь, в течение которой он будет перекладывать заряды между ракетами, чтобы снова получить $n$ ракет, в каждой из которых по два заряда одного вида. Для этого в его распоряжении есть еще одна $n + 1$-я ракета, в которой не лежит ни одного заряда. За одно действие пиротехник

1. выбирает ракету номер $i,ドル в которой есть хотя бы один заряд;
2. выбирает ракету номер $j \neq i,ドル в которой строго меньше двух зарядов;
3. перекладывает верхний заряд из ракеты $i$ наверх в ракету номер $j$.

Поскольку пиротехник не хочет тратить на это слишком много времени, он просит вас помочь ему найти способ получить $n$ ракет с парами одинаковых зарядов за не более чем 2ドルn$ таких действий.

입력

В первой строке дано целое число $n$ --- количество ракет, заготовленных для фейерверка (1ドル \leqslant n \leqslant 10^5$).

В $i$-й из следующий $n$ строк дано описание текущего состояния $i$-й ракеты: через пробел даны $x_{i_1}$ и $x_{i_2}$ --- номера нижнего и верхнего зарядов, находящихся в ней (1ドル \leqslant x_{i_1}, x_{i_2} \leqslant n$). Гарантируется, что каждое число от 1ドル$ до $n$ встречается ровно дважды в описаниях ракет. Ракета номер $n + 1$ изначально пустая.

출력

В первой строке выводите целое число $k$ --- количество действий, которое понадобится пиротехнику (0ドル \leqslant k \leqslant 2n$).

В следующих $k$ строках выведите описания действий в порядке их следования. Каждое действие описывается номерами ракет (от 1ドル$ до $n + 1$), между которыми следует переложить верхний заряд. Нельзя класть в ракету более двух зарядов и нельзя перекладывать заряд из ракеты в нее же (зачем делать бесполезные действия?).

Обратите внимание, что от вас не требуется минимизировать количество действий --- достаточно просто добиться того, чтобы их было не больше 2ドルn$.

제한

힌트