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

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

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

За одно действие пиротехник

• выбирает ракету номер i, в которой есть хотя бы один заряд;
• выбирает ракету номер j ≠ i, в которой строго меньше двух зарядов;
• перекладывает верхний заряд из ракеты i наверх в ракету номер j.

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

Формат входных данных

В первой строке дано целое число n — количество ракет, заготовленных для фейерверка (1 ≤ n ≤ 10⁵).

В i-й из следующий n строк дано описание текущего состояния i-й ракеты: через пробел даны x_i1 и x_i2 — номера нижнего и верхнего зарядов, находящихся в ней (1 ≤ x_i1, x_i2 ≤ n). Гарантируется, что каждое число от 1 до n встречается ровно дважды в описаниях ракет. Ракета номер n+1 изначально пустая.

Формат выходных данных

В первой строке выводите целое число k — количество действий, которое понадобится пиротехнику (0 ≤ k ≤ 2n).

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

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

Пример