Двусвязный список — одна из фундаментальных структур данных. Двусвязный список представляет собой последовательность элементов, в каждом из которых содержится информация о предыдущем и следующем элементах списка. В этой задаче все списки имеют линейную структуру: то есть у каждого элемента списка кроме первого есть ровно один предыдущий элемент, у каждого элемента списка кроме последнего есть ровно один следующий элемент, список не замкнут в цикл.
В этой задаче вам даны n ячеек памяти, образующие один или более двусвязных списков. Каждая ячейка памяти содержит информацию об элементе одного из списков. Ячейки памяти пронумерованы от 1 до n.
Для каждой ячейки памяти i известен номер ячейки, в которой содержится предыдущий элемент списка (величина li) и номер ячейки, в которой содержится следующий элемент списка (величина ri). Если ячейка памяти i содержит информацию о таком элементе, у которого нет предыдущего элемента в списке, то li = 0. Аналогично, если ячейка памяти i содержит информацию о таком элементе, у которого нет следующего элемента в списке, то ri = 0.
На рисунке изображены три списка. Например, для рисунка выше значения l и r следующие: l1 = 4, r1 = 7; l2 = 5, r2 = 0; l3 = 0, r3 = 0; l4 = 6, r4 = 1; l5 = 0, r5 = 2; l6 = 0, r6 = 4; l7 = 1, r7 = 0.
Объедините все заданные списки в один, подсоединив их друг к другу в любом порядке. В частности, если входные данные уже содержат один список, то каких-либо действий производить не надо. Выведите результирующий список в виде пар значений li, ri.
Каких-либо других действий, кроме как подсоединений начала одного списка к концу другого, совершать нельзя.
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 100) — количество ячеек памяти, в которых расположены двусвязные списки.
Следующие n строк содержат по два целых числа li, ri (0 ≤ li, ri ≤ n) — номера ячеек памяти предыдущего и следующего элемента списка для ячейки памяти i. Величина li = 0, если у элемента ячейки памяти i нет предыдущего элемента в его списке. Величина ri = 0, если у элемента ячейки памяти i нет следующего в его списке.
Гарантируется, что входные данные содержат описание одного или более двусвязных списков. Все списки имеют линейную структуру: то есть у каждого элемента списка кроме первого есть ровно один предыдущий элемент, у каждого элемента списка кроме последнего есть ровно один следующий элемент, список не замкнут в цикл. Каждая ячейка памяти содержит информацию об одном элементе некоторого списка, каждый элемент каждого списка записан в одной из n заданных ячеек.
Выведите n строк, i-я из строк должна содержать величины li и ri — номера ячеек памяти предыдущего и следующего элемента списка для ячейки памяти i после объединения всех списков из входных данных в один. Если решений несколько, выведите любое из них.
7
4 7
5 0
0 0
6 1
0 2
0 4
1 0
4 7
5 6
0 5
6 1
3 2
2 4
1 0
