← 返回题目列表

Codeforces · 847/A

A. 双向链表并集

中文机器翻译题面 查看原题

双向链表是基本数据结构之一。双向链表是一个元素序列,每个元素都包含有关该列表的前一个和下一个元素的信息。在这个问题中,所有列表都具有线性结构。 IE。除第一个元素之外的每个元素都恰好有一个前一个元素,除了最后一个元素之外的每个元素都恰好有一个下一个元素。该列表在循环中不是封闭的。

在此问题中,给定 n 个存储单元,形成一个或多个双向链表。每个单元格都包含有关某个列表中元素的信息。存储单元从 1 到 n 编号。

对于每个单元格 i,您将获得两个值:

- li — 包含单元格 i 中元素的前一个元素的单元格;
- ri — 包含单元格 i 中元素的下一个元素的单元格。

如果单元格 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 的列表的前一个和下一个元素的单元格。如果单元格 i 中的元素在其列表中没有前一个元素,则值 li = 0。如果单元格 i 中的元素在其列表中没有下一个元素,则值 ri = 0。

保证输入包含单个或多个双向链表的正确描述。所有列表都具有线性结构:列表中除第一个元素之外的每个元素都恰好有一个前一个元素;列表中除最后一个元素之外的每个元素都恰好有一个下一个元素。每个存储单元包含有关某个列表中的一个元素的信息,每个列表的每个元素都写入 n 个给定单元之一。

输出

打印 n 行,第 i 行必须包含两个整数 li 和 ri — 在输入的所有列表合并到一个列表中后,单元格 i 的列表的前一个和下一个元素的单元格。如果有很多解决方案,请打印其中任何一个。

示例

输入 #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