问题 G: cats 的数据结构

cats 刚刚学习了堆这个数据结构，不过他觉得二叉树的情况太简单了，想把它推广到任意结构的有根树 上。

现在 cats 有一个以 1 为根节点的树，树上的每个节点 i 都有两个整数权值 ai , bi。现在你需要为每个节 点确定权值 ai , bi，使得这个树满足以下四个条件。

1. 对于任意的 i (1 ≤ i ≤ n)，都有 1 ≤ ai , bi ≤ 10^9。 

2. 对于任意的一对 u, v (1 ≤ u, v ≤ n, u != v)，都有 au != av 且 bu != bv。

 3. 对于任意的一对 u, v (1 ≤ u, v ≤ n, u != v)，若 u 是 v 的祖先，则 au > av 且 bu > bv。 

4. 对于任意的一对 u, v (1 ≤ u, v ≤ n, u != v)，若 au > av 且 bu > bv，则 u 是 v 的祖先。

可以证明存在至少一种合法的构造方式，你需要给出所有合法构造方式中使序列 a1, b1, a2, b2, . . . an, bn 字典序最小的解。 

注 1：在一个有根树上，节点 u 为节点 v 的祖先，当且仅当所有的以 v 为起点，以根节点为终点的树上 路径都经过 u。 

注 2：两个相同长度的序列 a, b（a 与 b 至少存在一个位置不相同）的字典序比较方式为，对于最小的满 足 ai != bi 的 i，若 ai < bi 则序列 a 的字典序更小，若 ai > bi 则序列 b 的字典序更小。