新年的新航线
舒克和贝塔成立了一家航空公司。因为新年的来临，舒克贝塔打算重新规划航空路线。
舒克和贝塔的航空公司控制了 $n$ 个机场，这 $n$ 个机场的位置在地图上可看做一个正 $n$ 边形的 $n$ 个顶点，按顺时针依次编号为 $1, \dots, n$。
舒克和贝塔的航空公司掌握着这 $n$ 个机场间的 $2n-3$ 条双向航线，且他们恰好构成了这个正 $n$ 边形的所有边和一个三角剖分。也即，如果把机场作为点，航线作为线画在地图上，那么我们可以看到这些航线只可能在端点处相交，且最外围的航线构成了那个正 $n$ 边形的边，而正 $n$ 边形内部被其他航线完全分成了一个个三角形。
新年来了，航空公司人员纷纷放假，所以舒克希望新规范的航线图，航线尽量少，但要保证乘客能从原来的航线图的任何两个地方往返（也就是说你希望找一棵原图的生成树）。
同时，为了提高运力，贝塔希望新规范的航线图，不存在一个机场恰好能和两个机场直接通过航线相连（也就是说任何一个节点的度数不为 $2$）。
此外，受到航空管制的影响，你不能额外申请航线，只能取消部分航线。
现在它们找到了跳蚤，希望能帮助它们找出一个合法的方案。
输入格式
第一行一个整数 $n$。
接下来输入航线图。首先，在接下来 $n-3$ 行，第 $i$ 行两个整数 $i,j$，表示一条连接凸多边形顺时针方向上第 $i$ 个点和第 $j$ 个点的一条边。保证 $1 \le i, j \le n$。
同时，图中还有 $n$ 条多边形的边，第 $i$ 条连接凸多边形顺时针方向上第 $i$ 个点和第 $(i \bmod n)+1$ 个点的一条边。这些边将不会在输入中给出。
保证输入的边可以被看成是一个合法的三角剖分。
输出格式
如果无解输出 $-1$。
否则输出 $n-1$ 行，一行两个数字 $x,y$，表示你选择的航线。
4
1 3
1 2
1 3
1 4
3
-1
样例三、四、五
见样例数据下载
限制与约定
| 子任务编号 | $n$ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $\le 10$ | 无 | 20 |
| $2$ | $\le 400$ | 20 | |
| $3$ | $\le 5000$ | 20 | |
| $4$ | $\le 100000$ | 20 | |
| $5$ | $\le 500000$ | 三角剖分随机生成 | 10 |
| $6$ | 无 | 10 |
第五个子任务数据随机生成的方式为：
- 对一个凸多边形，如果点数不超过3则退出
- 否则随机两个不相邻的顶点，在它们之间连边，并对剩余两部分递归处理。
对于所有测试数据，满足 $3 \leq n \leq 500000$。
时间限制：$\texttt{2s}$
空间限制：$\texttt{512MB}$