舒克和贝塔成立了一家航空公司。因为新年的来临，舒克贝塔打算重新规划航空路线。

舒克和贝塔的航空公司控制了 $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$ 个点和第 $(imodn)+1$ 个点的一条边。这些边将不会在输入中给出。

保证输入的边可以被看成是一个合法的三角剖分。

输出格式

如果无解输出 $-1$。

否则输出 $n-1$ 行，一行两个数字 $x,y$，表示你选择的航线。

样例一

input

4
1 3

output

1 2
1 3
1 4

样例二

input

3

output

-1

样例三、四、五

见样例数据下载

限制与约定

第五个子任务数据随机生成的方式为：

• 对一个凸多边形，如果点数不超过3则退出
• 否则随机两个不相邻的顶点，在它们之间连边，并对剩余两部分递归处理。

对于所有测试数据，满足 $3\le n\le 500000$。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载