题目描述

有一个正 $n$ 边形，顶点按顺时针方向从 $1$ 到 $n$ 依次标号。给定这个多边形的 $n-3$ 条互不相同的对角线，满足它们互相之间只可能在顶点处相交。这样我们得到了一张 $n$ 个点，$2n-3$ 条边的无向图。

凸多边形的对角线指的是连接两个不相同且不在多边形上相邻的顶点的一条线段。

实际上，这个无向图可以是任意一个凸 $n$ 边形的三角剖分图。

你需要构造这个无向图的一棵生成树，使得每个点的度数都是奇数，或报告无解。

输入格式

第一行，一个整数，表示 $n$。

接下来 $n-3$ 行，每行两个整数 $u,v$ 表示一条给定的对角线 $(u,v)$。

输出格式

如果无解，那么输出一行一个整数 $-1$。

如果有解，那么输出 $n-1$ 行，每行两个数 $u,v$ 表示你所构造的答案中的一条边 $(u,v)$。

5
1 3
1 4

-1

8
6 8
5 8
2 4
2 5
1 5

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

提示

对于 $100\%$ 的数据，$3\le n\le 3\times 10^5$。

$\operatorname{Subtask} 1(9\%)$：$n\le 10$。

$\operatorname{Subtask} 2(1\%)$：$n$ 为奇数。

$\operatorname{Subtask} 3(10\%)$：$u=1$。

$\operatorname{Subtask} 4(30\%)$：$n\le 100$。

$\operatorname{Subtask} 5(30\%)$：$n\le 5\times 10^3$。

$\operatorname{Subtask} 6(20\%)$：无特殊限制。