410153: GYM103965 G Шоу фейерверков

G. Шоу фейерверковограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

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

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

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

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

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

Входные данные

В первой строке дано целое число $$$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$$$), между которыми следует переложить верхний заряд. Нельзя класть в ракету более двух зарядов и нельзя перекладывать заряд из ракеты в нее же (зачем делать бесполезные действия?).

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

ПримерыВходные данные

3
2 1
3 3
1 2

Выходные данные

3
1 4
3 1
4 3

Входные данные

5
1 5
2 3
3 5
4 2
1 4

Выходные данные

6
1 6
3 6
2 3
4 2
5 4
5 1