← 返回题目列表

Codeforces · 1283/F

F. DIY 花环

中文机器翻译题面 查看原题

波旅甲决定装饰他的房间,因为新年快到了。坡旅甲将安装的主要装饰品之一是他要自己焊接的花环。

由一根电线连接的几盏灯组成的简单花环对于波利卡普来说太无聊了。他将焊接一个由 $$$n$$$ 灯和 $$$n - 1$$$ 电线组成的花环。恰好一盏灯将连接到电网,电力将通过电线从该灯传输到其他灯。每根电线恰好连接两个灯;一盏灯称为该电线的主灯(从其他电线获取电力并将其传输到该电线的灯),另一盏称为辅助灯(从该电线获取电力的灯)。显然,每个灯最多有一根电线为其供电(该灯是该电线的辅助灯,并且是直接与其连接的所有其他电线的主灯)。

每个灯都有一个与其关联的亮度值,第 $$$i$$$ 个灯的亮度为 $$$2^i$$$。我们将电线的重要性定义为如果电线被切断(并且所有其他电线仍在工作),则所有与电网断开连接的灯的亮度值之和。

Polycarp画出了他想要制作的花环的方案(该方案描绘了所有$$$n$$$灯和$$$n - 1$$$电线,并且标记了将直接连接到电网的灯;电线的放置方式使得电力可以传输到每个灯)。之后,波利卡普计算出每根电线的重要性,按照重要性降序从 $$$1$$$ 到 $$$n - 1$$$ 进行枚举,然后为每根电线写下主灯的索引(按照从第一根电线到最后一根电线的顺序)。

第二天,波利卡普购买了花环所需的所有组件,并决定焊接它 - 但他找不到该方案。幸运的是,波利卡普找到了所有电线的主灯索引列表。你能帮他恢复原来的计划吗?

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 灯的数量。

第二行包含 $$$n - 1$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n - 1}$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 根电线的主灯索引(电线编号为重要性降序排列)。

输出

如果无法恢复原来的方案,则打印一个整数$$$-1$$$。

否则打印方案如下。在第一行中,打印一个整数 $$$k$$$ ($$$1 \le k \le n$$$) — 连接到电网的灯的索引。然后打印 $$$n - 1$$$ 行,每行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — 通过某些电线连接的灯的索引。电线(以及通过电线连接的灯)的描述可以按任何顺序打印。打印的描述必须对应于花环的方案,以便波利卡普可以从中写出列表$$$a_1$$$、$$$a_2$$$、...、$$$a_{n - 1}$$$。如果有多个这样的方案,则输出其中任何一个。

示例

输入 #1

6
3 6 3 1 5

输出 #1

3
6 3
6 5
1 3
1 4
5 2

注意

第一个示例的方案(R表示连接到电网的灯,电线上的数字是其重要性值):