Двусвязный список — одна из фундаментальных структур данных. Двусвязный список представляет собой последовательность элементов, в каждом из которых содержится информация о предыдущем и следующем элементах списка. В этой задаче все списки имеют линейную структуру: то есть у каждого элемента списка кроме первого есть ровно один предыдущий элемент, у каждого элемента списка кроме последнего есть ровно один следующий элемент, список не замкнут в цикл.
В этой задаче вам даны 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 строк, i-я из строк должна содержать величины li и ri — номера ячеек памяти предыдущего и следующего элемента списка для ячейки памяти i после объединения всех списков из входных данных в один. Если решений несколько, выведите любое из них.