题意：
现有一颗有根树，每个结点(i)有权值(2^i)，每条边有权值为这条边连接的深度较大的结点的子树权值和。
但现在并不知道这颗树的形态。
现在只会给出以下信息：按照边的权值从大到小进行排序，然后依次给出每条边的父亲结点。
现在要确定这颗树的形态。
思路：
假设每次给出的父亲结点为(p_i)，那么显然(p_1)为根节点。
注意，因为每个结点的权值为(2^i)，那么可以知道我们会依次找(2^n,2^{n-1},cdots,2^1)这些结点的位置。根据这一点，可以直接分情况讨论：
- 记录一个变量(now)为目前需要找的结点。
- 若(p_i)已存在，说明要新产生一颗子树，并且(now)结点已找到，为(p_{i-1})的儿子；
- 若(p_i)不存在，那么就是继续在寻找(now)结点，继续往当前子树深入即可。
注意用一个数组来标记结点是否找到。
细节见代码：
/*
* Author: heyuhhh
* Created Time: 2020/3/1 15:51:31
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
int n;
int a[N];
bool chk[N];
void run(){
vector <pii> edges;
for(int i = 1; i < n; i++) cin >> a[i];
int rt = a[1];
chk[rt] = true;
cout << rt << '
';
int now = n;
while(chk[now]) --now;
for(int i = 2; i < n; i++) {
if(!chk[a[i]]) {
edges.push_back(MP(rt, a[i]));
rt = a[i];
chk[rt] = true;
} else {
edges.push_back(MP(rt, now));
chk[now] = true;
rt = a[i];
}
while(chk[now]) --now;
}
assert(now > 0);
edges.push_back(MP(rt, now));
for(auto it : edges) {
cout << it.fi << ' ' << it.se << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> n) run();
return 0;
}