P4006 小 Y 和二叉树

小 Y 是一个心灵手巧的 OIer，她有许多二叉树模型。 小 Y 的二叉树模型中，每个结点都具有一个编号，小 Y 把她最喜欢的一个二叉树模型挂在了墙上，树根在最上面，左右子树分别在树根的左下方与右下方，且他们也都满足这样的悬挂规则。为了让这个模型更加美观，小 Y 选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法。所谓中序遍历最小，就是指中序遍历的结点编号序列的字典序最小。 一天，这个模型不小心被掉在了地上，幸运的是，所有结点和边都没摔坏，但是她想不起这个模型原来是怎么悬挂的了，也就是说：她想不起来树根节点的编号了。 小 Y 最近忙于准备清华集训，所以没太多时间处理别的事情，她只好找到同样心灵手巧的你帮忙复原她的二叉树模型。

无

无

 【子任务】  本题共 $20$ 个测试点，每个测试点 $5$ 分。各个测试点的数据范围如下： 随机数据的生成方式如下：对于第 $13$ 个测试点，从一棵两个结点的树开始，每次随机一个树上的度数为 $1$ 的结点（即叶结点），并生成两个与之直接相连的结点，直到这棵树上有 $n$ 个结点。显然，在这个测试点中， $n$ 是一个偶数。对于第 $15$ 和第 $16$ 个测试点，从一棵一个结点的树开始，每次随机一个树上的度数不超过 $2$ 的结点，并生成一个与之直接相连的结点，直到这棵树上有 $n$ 个结点。 【提示】 我们提供了一个只包含输入和输出功能的程序 `binary\_sample.cpp`。关于该程序的说明，见 `readme.txt`。你可以在答题时使用该程序的代码，也可以不使用，这将与你的得分无关。