双向链表是基本数据结构之一。双向链表是一个元素序列,每个元素都包含有关该列表的前一个和下一个元素的信息。在这个问题中,所有列表都具有线性结构。 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