CF1283F DIY Garland

Polycarp 决定装饰他的房间，因为新年快到了。他打算自己焊接一串彩灯作为主要装饰之一。 对于 Polycarp 来说，只用一根线连接几盏灯的简单彩灯太无聊了。他打算焊接一串由 $n$ 盏灯和 $n-1$ 根导线组成的彩灯。恰好有一盏灯会直接连接到电源，电力将通过导线从这盏灯传递到其他灯。每根导线恰好连接两盏灯；其中一盏称为这根导线的主灯（它从其他导线获得电力并将电力传递到这根导线上），另一盏称为辅助灯（它通过这根导线获得电力）。显然，每盏灯至多只有一根导线为其供电（这时该灯是这根导线的辅助灯，同时是所有直接与其相连的其他导线的主灯）。 每盏灯都有一个亮度值，第 $i$ 盏灯的亮度为 $2^i$。我们定义一根导线的重要性为：如果切断这根导线（其余导线仍然工作），所有因此与电源断开的灯的亮度值之和。 Polycarp 已经画好了他想要制作的彩灯电路图（电路图展示了所有 $n$ 盏灯和 $n-1$ 根导线，并标记了直接连接到电源的那盏灯；导线的连接方式保证每盏灯都能获得电力）。之后，Polycarp 计算了每根导线的重要性，将它们按重要性从高到低编号为 $1$ 到 $n-1$，然后记录下每根导线的主灯编号（按导线重要性从高到低的顺序）。 第二天，Polycarp 买齐了所有彩灯的元件，准备开始焊接——但他找不到电路图了。幸运的是，Polycarp 找到了所有导线主灯编号的列表。你能帮他还原出原始的电路图吗？

第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示灯的数量。 第二行包含 $n-1$ 个整数 $a_1, a_2, \ldots, 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$），表示有一根导线连接了编号为 $x_i$ 和 $y_i$ 的两盏灯。每根导线的描述（以及其连接的灯）可以按任意顺序输出。输出的电路图必须保证 Polycarp 能够根据它写出列表 $a_1, a_2, \ldots, a_{n-1}$。如果存在多种方案，输出任意一种即可。

第一个样例的电路图如下（R 表示连接到电源的灯，导线上的数字为其重要性）：  由 ChatGPT 4.1 翻译