Union of Doubly Linked Lists

题意翻译

双向链表是一种基本的数据结构。一个双向链表是一串元素序列。链表中每一个元素都链接着它前面和后面的元素。在这个问题中，这个链表是一个线性序列。除了第一个元素外，每个元素都有一个直接前导；除了最后一个元素外，每个元素都有一个直接后继。这个链表不形成一个环。 在这个问题中，你被给予了$n$个单元。这些单元能够形成一个或者多个双向链表。每个单元包含着一些链表元素的信息。这些单元的编号是从$1$至$n$的。 对于每个单元，有两个属性： $l_i$表示第$i$个单元的前导； $r_i$表示第$i$个单元的后继。 如果$l_i=0$，表示这个单元没有直接前导。如果$r_i=0$，表示这个单元没有直接后继。 对于题目描述所给出的图来说： | $i$ | $l_{i}$ | $r_{i}$ | | ---- | ------- | ------- | | 1 | 4 | 7 | | 2 | 5 | 0 | | 3 | 0 | 0 | | 4 | 6 | 1 | | 5 | 0 | 2 | | 6 | 0 | 4 | | 7 | 1 | 0 | 你的任务是，给定若干个由如上方式表示的双向链表，链接这些双向链表使得其仅构成一个双向链表。注意：你只能通过链接两个双向链表的首尾单元来链接这两个双向链表。 输入格式：第一行一个数$n(1\leq n\leq100)$，表示单元的个数。后$n$行每行$2$个数$l_i$和$r_i$，这既是描述了一个单元的属性，也描述了双向链表的结构。 输出格式：$n$行，每行两个数$l_i$和$r_i$，表示在将所有元素链接成一个双向链表后，第$i$个单元新的属性值。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

7
4 7
5 0
0 0
6 1
0 2
0 4
1 0

输出样例 #1

4 7
5 6
0 5
6 1
3 2
2 4
1 0