你是 ICPC 公司的一名经理。公司大楼里有 $N$ 台计算机，编号从 $1$ 到 $N$。有 $N - 1$ 条电缆，编号从 $1$ 到 $N - 1$，将所有计算机连接成一个单一的网络。电缆 $i$ 连接计算机 $U_i$ 和 $V_i$。

通过研究，未来可能会发生 $N - 1$ 个等级的灾难，编号从 $1$ 到 $N - 1$。在灾难等级 $x$ 下，所有满足 $1 \le i \le x$ 的电缆 $i$ 都会损坏。损坏的电缆不能用于连接。

作为经理，你需要制定一个应急预案。在你的应急预案中，应该有 $N - 1$ 条备用电缆，编号从 $1$ 到 $N - 1$。如果现有的电缆 $i$ 损坏，则部署备用电缆 $i$ 来连接计算机 $A_i$ 和 $B_i$。如果现有的电缆 $i$ 没有损坏，则不部署备用电缆 $i$，且该备用电缆不用于连接。

对于每个灾难等级，备用电缆与未损坏的电缆必须保持所有计算机连接成一个单一的网络。此外，出于实际考虑，如果连接计算机 $u$ 和 $v$ 的电缆已经存在，那么在你的应急预案中就不应该有任何连接计算机 $u$ 和 $v$ 的备用电缆。

请创建一个满足所有要求的应急预案，或者确定这样的预案是否无法创建。如果存在多个应急预案，选择其中任何一个即可。

输入格式

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

输出格式

如果可以创建应急预案，则输出 $N - 1$ 行，表示满足所有要求的应急预案。每行包含两个整数 $A_i, B_i$ ($1 \le A_i, B_i \le N$)，表示备用电缆 $i$。如果存在多个应急预案，输出其中任何一个即可。

如果无法创建应急预案，则输出 $-1$。

样例

样例输入 1

7
1 2
3 7
2 4
2 5
1 3
3 6

样例输出 1

3 5
6 7
4 6
2 3
1 7
3 4

说明 1

下图展示了该样例。圆圈代表计算机，黑线和红色虚线分别代表现有电缆和备用电缆。图中未显示损坏的电缆。

样例输入 2

3
1 2
2 3

样例输出 2

-1

说明 2

应急预案中应该有 $2$ 条备用电缆。你只能拥有一条备用电缆，它将连接计算机 $1$ 和 $3$。其余的配对已经由当前的电缆连接。