CF1906I.Contingency Plan 2

You are working as a manager in The ICPC Company. In the company building, there are $N$ computers (numbered from $1$ to $N$). There are $N - 1$ cables, numbered from $1$ to $N - 1$, that connect all the computers into a single network. Cable $i$ connects computer $U_i$ and $V_i$. Each cable can be set into emergency mode, where cable $i$ only transfers data from computer $U_i$ to computer $V_i$, but not the other way around. During a disaster, it is mandatory for all cables to be in emergency mode.

Through your research, you discover a new way to determine the vulnerability of a network. You want to add zero or more new cables to the current network such that it is not vulnerable during a disaster. Your network is not vulnerable if and only if there is exactly one permutation of $1$ to $N$ such that $u$ appears before $v$ in the permutation for all cables that connect computer $u$ and $v$. In other words, it should have exactly one topological order.

The following illustration shows examples of not vulnerable networks and vulnerable networks.

For the not vulnerable networks, the only permutation that satisfies the requirement for the networks on the left and on the right are $[1, 2, 3]$ and $[3, 1, 2]$, respectively. Meanwhile, for the vulnerable networks, there are $2$ permutations that satisfy the requirement for the network on the left: $[1, 2, 3]$ and $[3, 1, 2]$; while there is no permutation that satisfies the requirement for the network on the right.

You are interested in the minimum number of new cables that should be added to the current network such that it is not vulnerable during a disaster. Furthermore, you want to know, which pairs of computers should be connected by using the minimum number of cables. If there are several ways to connect, you can connect in any way of your choice. Under the given constraints, it can be proven that there exists a way to make the network not vulnerable.

你正在 ICPC 公司担任经理。在公司大楼中，共有 $N$ 台计算机（编号从 $1$ 到 $N$）。有 $N - 1$ 根电缆（编号从 $1$ 到 $N - 1$），将所有计算机连接成一个连通网络。第 $i$ 根电缆连接计算机 $U_i$ 和 $V_i$。每根电缆均可设置为“应急模式”，此时第 $i$ 根电缆仅允许数据从计算机 $U_i$ 单向传输至计算机 $V_i$，而不可反向传输。在灾难发生期间，所有电缆必须处于应急模式。

通过研究，你发现了一种评估网络脆弱性的新方法。你希望向当前网络中添加零条或多条新电缆，使得该网络在灾难期间不具有脆弱性。当且仅当存在唯一一个 $1$ 到 $N$ 的排列，使得对每一条连接计算机 $u$ 与 $v$ 的电缆，$u$ 在该排列中均出现在 $v$ 之前时，网络才被视为不具有脆弱性。换言之，该有向图应恰好拥有唯一一个拓扑序。

下图展示了若干“不脆弱网络”与“脆弱网络”的示例：

对于图中两个“不脆弱网络”，分别仅存在唯一满足条件的排列：左侧网络为 $[1, 2, 3]$，右侧网络为 $[3, 1, 2]$。而对于两个“脆弱网络”，左侧网络存在两个满足条件的排列：$[1, 2, 3]$ 和 $[3, 1, 2]$；右侧网络则不存在任何满足条件的排列。

你关心的是：为使当前网络在灾难期间不具有脆弱性，所需添加的最少电缆数量是多少？此外，你还希望知道：在使用该最少数量电缆的前提下，应将哪些计算机对连接起来？若存在多种可行方案，任选其一即可。在本题给定约束下，可以证明：总存在一种方式使网络变得不脆弱。

The first line consists of an integer $N$ ($2 \leq N \leq 100\,000$).

Each of the next $N - 1$ lines consists of two integers $U_i$ $V_i$ ($1 \leq U_i, V_i \leq N$). The input edges form a tree.

第一行包含一个整数 $N$（$2 \leq N \leq 100\,000$）。

接下来的 $N - 1$ 行，每行包含两个整数 $U_i$ 和 $V_i$（$1 \leq U_i, V_i \leq N$）。输入的边构成一棵树。

The first line consists of an integer, representing the minimum number of new cables that should be added to the current network such that it is no longer vulnerable during a disaster. Denote this number as $K$ and the new cables are numbered from $1$ to $K$.

If $K$ is not $0$, then output $K$ lines. Each of the next $K$ lines consists of two integers $A_i$ $B_i$, representing the computers that are connected by the new cable $i$. During a disaster, new cable $i$ only transfers data from computer $A_i$ to computer $B_i$, but not the other way around. If there exist several solutions, you can output any of them.

第一行包含一个整数，表示为使当前网络在灾难期间不再脆弱，所需新增电缆的最少数量。将该数量记为 $K$，新增电缆编号为 $1$ 至 $K$。

若 $K \neq 0$，则输出 $K$ 行。接下来的每行包含两个整数 $A_i$ 和 $B_i$，表示新增电缆 $i$ 所连接的两台计算机。在灾难期间，新增电缆 $i$ 仅能从计算机 $A_i$ 向计算机 $B_i$ 传输数据，而不能反向传输。若存在多种可行解，输出任意一种即可。

Explanation for the sample input/output #3

The following illustration shows the original network and the new network with the added cables during a disaster. The only permutation that satisfies the requirement is $[1, 2, 3, 4, 5]$.

样例输入/输出 #3 的说明

以下示意图展示了原始网络以及灾难期间新增电缆后的新网络。唯一满足要求的排列是 $[1, 2, 3, 4, 5]$。