cats 的数据结构

Problem Description

此题输入/输出量较大，建议使用较快的读入方式，时间限制以关闭流同步的 cin/cout 为标准 cats 刚刚学习了堆这个数据结构，不过他觉得二叉树的情况太简单了，想把它推广到任意结构的有根树上。 现在 cats 有一个以 $1$ 为根节点的树，树上的每个节点 $i$ 都有两个整数权值 $a_i,b_i$。现在你需要为每个节点确定权值 $a_i,b_i$，使得这个树满足以下四个条件。

1. 对于任意的 $i$ $(1\leq i\leq n)$，都有 $1\leq a_i,b_i\leq 10^9$。
2. 对于任意的一对 $u,v$ $(1\leq u,v\leq n,u\neq v)$，都有 $a_u\neq a_v$ 且 $b_u\neq b_v$。
3. 对于任意的一对 $u,v$ $(1\leq u,v\leq n,u\neq v)$，若 $u$ 是 $v$ 的祖先，则 $a_u>a_v$ 且 $b_u>b_v$。
4. 对于任意的一对 $u,v$ $(1\leq u,v\leq n,u\neq v)$，若 $a_u>a_v$ 且 $b_u>b_v$，则 $u$ 是 $v$ 的祖先。 可以证明存在至少一种合法的构造方式，你需要给出所有合法构造方式中使序列 $a_1,b_1,a_2,b_2,\dots a_n,b_n$ 字典序最小的解。 注 1：在一个有根树上，节点 $u$ 为节点 $v$ 的祖先，当且仅当所有的以 $v$ 为起点，以根节点为终点的树上路径都经过 $u$。 注 2：两个相同长度的序列 $a,b$（$a$ 与 $b$ 至少存在一个位置不相同）的字典序比较方式为，对于最小的满足 $a_i\neq b_i$ 的 $i$，若 $a_i < b_i$ 则序列 $a$ 的字典序更小，若 $a_i > b_i$ 则序列 $b$ 的字典序更小。

Input

第一行一个整数 $T$ $(1\leq T\leq 2000)$，表示测试数据的组数。 接下来包含 $T$ 组测试数据。 每组数据第一行一个整数 $n$ $(2\leq n\leq 2\cdot 10^5)$，表示 cats 给出的树的节点个数。 接下来一行包含 $n-1$ 个整数 $p_2,p_3,\cdots p_n$ $(1\leq p_i\leq n)$，依次表示编号为 $2$ 到 $n$ 的节点的父亲节点编号。保证输入的会构成一颗合法的以编号为 $1$ 的节点作为根节点的有根树。 保证所有测试数据的 $n$ 之和不超过 $10^6$。

Output

对于每一组测试数据输出一行 $2\cdot n$ 个由空格隔开的整数 $a_1,b_1,a_2,b_2,\dots a_n,b_n$，表示满足条件的字典序最小的序列。

Sample Input

3
3
1 1
5
1 1 3 3
4
4 1 3

Sample Output

3 3 1 2 2 1
5 5 1 4 4 3 2 2 3 1
4 4 1 1 3 3 2 2

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）