English · Original
Chinese · Translation
Formal · Original
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.
<center> Three lists are shown on the picture.</center>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.
## Input
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.
## Output
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.
[samples]
双向链表是一种基础的数据结构。双向链表是由若干元素组成的序列，每个元素包含关于其前一个和后一个元素的信息。在本题中，所有链表均为线性结构，即：除第一个元素外，每个元素有且仅有一个前驱元素；除最后一个元素外，每个元素有且仅有一个后继元素。链表不构成环。
本题中，你被给予 #cf_span[n] 个内存单元，这些单元构成一个或多个双向链表。每个单元包含某个链表中元素的信息。内存单元编号从 #cf_span[1] 到 #cf_span[n]。
对于每个单元 #cf_span[i]，你被给予两个值：
若单元 #cf_span[i] 包含的是没有前驱元素的元素，则 #cf_span[li = 0]；类似地，若单元 #cf_span[i] 包含的是没有后继元素的元素，则 #cf_span[ri = 0]。
例如，对于上图，#cf_span[l] 和 #cf_span[r] 的值如下：#cf_span[l1 = 4]，#cf_span[r1 = 7]；#cf_span[l2 = 5]，#cf_span[r2 = 0]；#cf_span[l3 = 0]，#cf_span[r3 = 0]；#cf_span[l4 = 6]，#cf_span[r4 = 1]；#cf_span[l5 = 0]，#cf_span[r5 = 2]；#cf_span[l6 = 0]，#cf_span[r6 = 4]；#cf_span[l7 = 1]，#cf_span[r7 = 0]。
你的任务是将所有给定的链表合并为一个链表，以任意顺序将它们首尾相连。特别地，如果输入数据已经是一个单独的链表，则无需执行任何操作。请输出合并后链表的 #cf_span[li] 和 #cf_span[ri] 值。
除了将一个链表的开头连接到另一个链表的末尾之外，不允许执行任何其他操作。
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——存放双向链表的内存单元数量。
接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[li], #cf_span[ri]（#cf_span[0 ≤ li, ri ≤ n]）——表示单元 #cf_span[i] 中元素的前驱和后继单元编号。若单元 #cf_span[i] 中的元素在其链表中没有前驱，则 #cf_span[li = 0]；若没有后继，则 #cf_span[ri = 0]。
保证输入数据正确描述了一个或多个双向链表。所有链表均为线性结构：每个链表中除第一个元素外，每个元素有且仅有一个前驱；除最后一个元素外，每个元素有且仅有一个后继。每个内存单元包含某个链表中一个元素的信息，每个链表的每个元素均被写入给定的 #cf_span[n] 个单元之一。
请输出 #cf_span[n] 行，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]——表示所有输入链表合并为一个链表后，单元 #cf_span[i] 中元素的前驱和后继单元编号。若有多种解法，输出任意一种即可。
## Input
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——存放双向链表的内存单元数量。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[li], #cf_span[ri]（#cf_span[0 ≤ li, ri ≤ n]）——表示单元 #cf_span[i] 中元素的前驱和后继单元编号。若单元 #cf_span[i] 中的元素在其链表中没有前驱，则 #cf_span[li = 0]；若没有后继，则 #cf_span[ri = 0]。保证输入数据正确描述了一个或多个双向链表。所有链表均为线性结构：每个链表中除第一个元素外，每个元素有且仅有一个前驱；除最后一个元素外，每个元素有且仅有一个后继。每个内存单元包含某个链表中一个元素的信息，每个链表的每个元素均被写入给定的 #cf_span[n] 个单元之一。
## Output
请输出 #cf_span[n] 行，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]——表示所有输入链表合并为一个链表后，单元 #cf_span[i] 中元素的前驱和后继单元编号。若有多种解法，输出任意一种即可。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of memory cells, indexed from $ 1 $ to $ n $.
For each cell $ i \in \{1, \dots, n\} $, define:
- $ l_i \in \{0, 1, \dots, n\} $: the index of the previous element, or $ 0 $ if none.
- $ r_i \in \{0, 1, \dots, n\} $: the index of the next element, or $ 0 $ if none.
The pairs $ (l_i, r_i) $ describe one or more disjoint linear doubly linked lists.
**Constraints**
1. $ 1 \leq n \leq 100 $
2. For all $ i $, $ 0 \leq l_i, r_i \leq n $
3. The structure is consistent:
- Each cell belongs to exactly one list.
- Each list is linear: no cycles, each non-head has exactly one predecessor, each non-tail has exactly one successor.
4. The input describes valid doubly linked lists.
**Objective**
Reconfigure the lists into a single doubly linked list by performing **only** the operation of linking the tail of one list to the head of another.
Let $ H \subseteq \{1, \dots, n\} $ be the set of head nodes: $ \{ i \mid l_i = 0 \} $
Let $ T \subseteq \{1, \dots, n\} $ be the set of tail nodes: $ \{ i \mid r_i = 0 \} $
Construct a new sequence of links $ (l_i', r_i') $ such that:
- All original intra-list links are preserved.
- Exactly one head $ h \in H $ satisfies $ l_h' = 0 $ (new global head).
- Exactly one tail $ t \in T $ satisfies $ r_t' = 0 $ (new global tail).
- For all other $ h' \in H \setminus \{h\} $, $ l_{h'}' \neq 0 $ (linked to some tail).
- For all other $ t' \in T \setminus \{t\} $, $ r_{t'}' \neq 0 $ (linked to some head).
- The new links form a single linear doubly linked list.
Output $ (l_i', r_i') $ for all $ i \in \{1, \dots, n\} $.
API Response (JSON)
{
"problem": {
"name": "A. Union of Doubly Linked Lists",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF847A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "双向链表是一种基础的数据结构。双向链表是由若干元素组成的序列，每个元素包含关于其前一个和后一个元素的信息。在本题中，所有链表均为线性结构，即：除第一个元素外，每个元素有且仅有一个前驱元素；除最后一个元素外，每个元素有且仅有一个后继元素。链表不构成环。\n\n本题中，你被给予 #cf_span[n] 个内存单元，这些单元构成一个或多个双向链表。每个单元包含某个链表中元素的信息。内存单元编号从 #cf_s...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of memory cells, indexed from $ 1 $ to $ n $. \nFor each cell $ i \\in \\{1, \\dots, n\\} $, define: \n- $ l_i \\in \\{0, 1, \\dots, n\\} $: the inde...",
"is_translate": false,
"language": "Formal"
}
]
}