此题输入/输出量较大，建议使用较快的读入方式，时间限制以关闭流同步的 cin/cout 为标准

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

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

• 对于任意的 $(1≤i≤n)$，都有 $1≤a_i ,b_i ≤10^9$ 。
• 对于任意的一对 $u,v (1≤u,v≤n,u \neq v)$，都有 $a_u\neq a_v$ 且 $b_u\neq b_v$ 。
• 对于任意的一对 $u,v (1≤u,v≤n,u\neq v)$，若 $u$ 是 $v$ 的祖先，则 $a_u\gt a_v$ 且 $b_u\gt b_v$。
• 对于任意的一对 $u,v (1≤u,v≤n,u\neq v)$，若 $a_u \gt a_v$ 且 $b_u\gt b_v$ ，则 $u$ 是 $v$ 的祖先。

可以证明存在至少一种合法的构造方式，你需要给出所有合法构造方式中使序列 $a_1,b_1,a_2,b_2,\cdots,a_n,b_n$ 字典序最小的解。

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

注 2：两个相同长度的序列 $a,b$（$a$ 与 $b$ 至少存在一个位置不相同）的字典序比较方式为，对于最小的满足 $a_i \neq =b_i$ 的 $i$，若 $a_i \lt b_i$ 则序列 $a$ 的字典序更小，若 $a_i \gt b_i$ 则序列 $b$ 的字典序更小。

第一行一个整数 $T (1≤T≤2000)$，表示测试数据的组数。

接下来包含 $T$ 组测试数据。

每组数据第一行一个整数 $n$ (2≤n≤2⋅10^5 )$，表示 cats 给出的树的节点个数。

接下来一行包含 $n−1$ 个整数 $p_2,p_3,\cdots,p_n(1≤p_i ≤n)$，依次表示编号为 $2$ 到 $n$ 的节点的父亲节点编号。保证输入的会构成一颗合法的以编号为 $1$ 的节点作为根节点的有根树。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

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