CF847A.Union of Doubly Linked Lists

Doubly linked list is one of the fundamental data structures. A doubly linked list is a sequence of elements, each containing information about the previous and the next elements of the list. In this problem all lists have linear structure. I.e. each element except the first has exactly one previous element, each element except the last has exactly one next element. The list is not closed in a cycle.

In this problem you are given n memory cells forming one or more doubly linked lists. Each cell contains information about element from some list. Memory cells are numbered from 1 to n.

For each cell i you are given two values:

• l__i — cell containing previous element for the element in the cell i;
• r__i — cell containing next element for the element in the cell i.

If cell i contains information about the element which has no previous element then l__i = 0. Similarly, if cell i contains information about the element which has no next element then r__i = 0.

Three lists are shown on the picture.

For example, for the picture above the values of l and r are the following: _l_1 = 4, _r_1 = 7; _l_2 = 5, _r_2 = 0; _l_3 = 0, _r_3 = 0; _l_4 = 6, _r_4 = 1; _l_5 = 0, _r_5 = 2; _l_6 = 0, _r_6 = 4; _l_7 = 1, _r_7 = 0.

Your task is to unite all given lists in a single list, joining them to each other in any order. In particular, if the input data already contains a single list, then there is no need to perform any actions. Print the resulting list in the form of values l__i, r__i.

Any other action, other than joining the beginning of one list to the end of another, can not be performed.

双向链表是最基本的数据结构之一。双向链表是一组元素的序列，其中每个元素均包含关于该链表中前一个元素和后一个元素的信息。在本题中，所有链表均具有线性结构：即除第一个元素外，每个元素恰好有一个前驱元素；除最后一个元素外，每个元素恰好有一个后继元素。链表不构成环。

在本题中，你将得到由 $n$ 个内存单元构成的一个或多个双向链表。每个内存单元包含某个链表中一个元素的信息。内存单元编号从 $1$ 到 $n$。

对每个内存单元 $i$，你将获得两个值：

• $l_i$ —— 存储单元 $i$ 中元素的前驱元素所在的内存单元编号；
• $r_i$ —— 存储单元 $i$ 中元素的后继元素所在的内存单元编号。

若单元 $i$ 中存储的是某链表的首元素（即无前驱元素），则 $l_i = 0$；类似地，若单元 $i$ 中存储的是某链表的尾元素（即无后继元素），则 $r_i = 0$。

图中展示了三条链表。

例如，对于上图，$l$ 和 $r$ 的取值如下：$l_1 = 4$, $r_1 = 7$；$l_2 = 5$, $r_2 = 0$；$l_3 = 0$, $r_3 = 0$；$l_4 = 6$, $r_4 = 1$；$l_5 = 0$, $r_5 = 2$；$l_6 = 0$, $r_6 = 4$；$l_7 = 1$, $r_7 = 0$。

你的任务是将所有给定的链表合并为一条单一链表，以任意顺序将它们首尾相连。特别地，若输入数据本身已构成一条链表，则无需执行任何操作。请以 $l_i$、$r_i$ 的形式输出合并后的链表。

除将某条链表的头节点连接至另一条链表的尾节点外，不允许执行其他任何操作。

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of memory cells where the doubly linked lists are located.

Each of the following n lines contains two integers l__i, r__i (0 ≤ l__i, r__i ≤ n) — the cells of the previous and the next element of list for cell i. Value l__i = 0 if element in cell i has no previous element in its list. Value r__i = 0 if element in cell i has no next element in its list.

It is guaranteed that the input contains the correct description of a single or more doubly linked lists. All lists have linear structure: each element of list except the first has exactly one previous element; each element of list except the last has exactly one next element. Each memory cell contains information about one element from some list, each element of each list written in one of n given cells.

第一行包含一个整数 $n$（$1 \leq n \leq 100$）—— 表示双向链表所处的内存单元数量。

接下来的 $n$ 行中，每行包含两个整数 $l_i$、$r_i$（$0 \leq l_i, r_i \leq n$）—— 分别表示第 $i$ 个单元中元素在其链表中的前驱单元编号和后继单元编号。若第 $i$ 个单元中的元素在其链表中没有前驱元素，则 $l_i = 0$；若没有后继元素，则 $r_i = 0$。

保证输入数据正确描述了一个或多个双向链表。所有链表均具有线性结构：除链表首元素外，每个链表元素恰好有一个前驱元素；除链表尾元素外，每个链表元素恰好有一个后继元素。每个内存单元存储某个链表中一个元素的信息，而每个链表的每个元素均存于给定的 $n$ 个单元之一中。

Print n lines, the i-th line must contain two integers l__i and r__i — the cells of the previous and the next element of list for cell i after all lists from the input are united in a single list. If there are many solutions print any of them.

输出 n 行，其中第 i 行必须包含两个整数 l__i 和 r__i —— 表示在将输入中的所有链表合并为一个链表后，第 i 个单元格的前驱单元格和后继单元格的编号。若存在多个解，输出任意一个即可。