P15624 [ICPC 2022 Jakarta R] Contingency Plan

你在 ICPC 公司担任经理。公司大楼内有 $N$ 台计算机，编号从 $1$ 到 $N$。有 $N - 1$ 条电缆，编号从 $1$ 到 $N - 1$，这些电缆将所有计算机连接成一个单一网络。电缆 $i$ 连接计算机 $U_i$ 和 $V_i$。 根据你的研究，未来可能发生 $N - 1$ 个级别的灾难，编号从 $1$ 到 $N - 1$。在灾难级别 $x$ 下，所有满足 $1 \leq i \leq x$ 的电缆 $i$ 都会损坏。损坏的电缆无法用于连接。 作为经理，你需要制定一个应急预案。在你的应急预案中，应该包含 $N - 1$ 条备用电缆，编号从 $1$ 到 $N - 1$。如果现有的电缆 $i$ 损坏，那么备用电缆 $i$ 将被部署，用于连接计算机 $A_i$ 和 $B_i$。如果现有的电缆 $i$ 没有损坏，那么备用电缆 $i$ 不会被部署，也不会用于连接。 对于每个灾难级别，备用电缆与未损坏的电缆一起，必须保持所有计算机连接在一个单一网络中。此外，出于实际原因，如果存在一条连接计算机 $u$ 和 $v$ 的电缆，那么在你的应急预案中，就不应该有任何备用电缆连接计算机 $u$ 和 $v$。 请创建一个满足所有要求的应急预案，或者确定这样的计划不可能实现。如果存在多个可行的应急预案，输出其中任意一个即可。

输入以一个整数 $N$（$2 \leq N \leq 100\,000$）开始，表示计算机的数量。接下来的 $N - 1$ 行，每行包含 $2$ 个整数 $U_i$ $V_i$（$1 \leq U_i, V_i \leq N$），表示电缆 $i$。所有电缆将所有计算机连接成一个单一网络。

如果应急预案可以创建，则输出包含 $N - 1$ 行，表示你满足所有要求的应急预案。每行包含 $2$ 个整数 $A_i$ $B_i$（$1 \leq A_i, B_i \leq N$），表示备用电缆 $i$。如果存在多个可行的应急预案，输出其中任意一个。 如果应急预案不可能创建，则在一行中输出 $-1$。

#### 样例输入/输出 #1 的解释 下图为本样例的示意图。圆圈代表计算机，黑色实线代表现有电缆，红色虚线代表备用电缆。图中未显示损坏的电缆。 :::align{center}  ::: #### 样例输入/输出 #2 的解释 应急预案中应该有 $2$ 条备用电缆。你只能有一条备用电缆，用于连接计算机 $1$ 和 $3$。其余计算机对之间已经由现有电缆连接。 翻译由 DeepSeek 完成