CSES1134 普鲁弗编码
#CS1134. 普鲁弗编码
普鲁弗编码
题目背景
翻译自 CSES-1134 题。
题目描述
一棵有 n 个节点的树的普鲁弗编码是一个包含 n−2n-2n−2 个整数的序列，唯一地指定了树的结构。
该编码的构造方法如下：只要树中剩余的节点至少有三个，找出最小标签的叶子节点，将其唯一邻居的标签添加到编码中，并从树中删除该叶子节点。
给定一棵树的普鲁弗编码，任务是根据这个编码构造原始的树。
输入格式
第一行输入一个整数 n，表示树的节点数。节点的编号为 1,2,…,n1, 2, \dots, n1,2,…,n。
第二行输入 n−2n-2n−2 个整数，表示树的普鲁弗编码。
输出格式
输出 n−1n-1n−1 行，描述树的边。每一行包含两个整数 a 和 b，表示节点 a 和节点 b 之间有一条边。你可以以任意顺序输出这些边。
样例
5
2 2 4
1 2
2 3
2 4
4 5
说明/提示