UOJ Logo Universal Online Judge

UOJ

#496. 新年的新航线

附件下载 统计

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

舒克和贝塔的航空公司控制了 $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$,表示你选择的航线。

样例一

input

4
1 3

output

1 2
1 3
1 4

样例二

input

3

output

-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}$

下载

样例数据下载