题目描述

众所周知，Arisa 是盆栽大王。今天，Arisa 希望在画布上画出利根川的结构。

利根川是一棵有 $n$ 个节点的有根二叉树，根节点的编号固定为 $1$。保证对于任意非根节点 $i$，其父节点 $f_i$ 满足 $f_i<i$。设节点 $i$ 的左儿子和右儿子分别为 $L_i$ 和 $R_i$。

Arisa 需要为每个节点分配一个整数坐标 $U_i=(x_i,y_i)$，其中 $|x_i|,|y_i|\le 10^8$，并满足以下条件：

任意两个节点的坐标不能相同；

对于二叉树中的每条边 $(u,v)$，其中 $u<v$，必须满足 $y_u<y_v$；

对于二叉树中的任意两条边 $(a,b)$ 和 $(c,d)$，线段 $U_aU_b$ 与 $U_cU_d$ 不允许相交或重合，但允许共用端点；

对于任意节点 $i$，若其左儿子存在，则左儿子的 $x$ 坐标不能大于 $x_i$；若其右儿子存在，则右儿子的 $x$ 坐标不能小于 $x_i$。即 $x_{L_i}\le x_i\le x_{R_i}$。

画布的大小有限，Arisa 使用的画布面积不能超过 $66666666$，即

$(\max_{1\le i\le n}x_i-\min_{1\le i\le n}x_i)\times(\max_{1\le i\le n}y_i-\min_{1\le i\le n}y_i)\le 66666666$。

请帮助 Arisa 找到一种坐标分配方案，使上述所有限制均得到满足。

可以证明，在题目给定的数据范围内，对于任意输入的二叉树，都至少存在一种满足全部条件的分配方案。

输入格式

本题单个测试点内包含多组测试数据。

第一行输入一个正整数 $T$（$1\le T\le 50$），表示测试数据的组数。

接下来依次输入 $T$ 组数据。对于每组数据：

第一行输入一个正整数 $n$（$1\le n\le 10^5$），表示二叉树的节点数；

接下来输入 $n$ 行，第 $i$ 行包含两个整数 $L_i,R_i$（$0\le L_i,R_i\le n$），表示节点 $i$ 的左儿子和右儿子。若节点 $i$ 没有左儿子，则 $L_i=0$；若节点 $i$ 没有右儿子，则 $R_i=0$。

保证输入的树是一棵以节点 $1$ 为根的二叉树。

输出格式

对于每组数据，输出 $n$ 行。第 $i$ 行输出两个用空格分隔的整数 $x_i,y_i$，表示分配给节点 $i$ 的坐标。

你需要保证 $|x_i|,|y_i|\le 10^8$。

本题使用 Special Judge 进行评测。如果有多种满足所有条件的坐标分配方案，你可以输出其中任意一种。

样例输入

2 7 2 3 4 5 6 7 0 0 0 0 0 0 0 0 4 2 0 0 3 4 0 0 0

样例输出

4 0 2 1 6 1 1 2 3 2 5 2 7 2 -1 -1 -1 0 -1 1 -1 2

样例说明

第一组数据使用的画布面积为 $(7-1)\times(2-0)=12$。

第二组数据的所有节点具有相同的 $x$ 坐标，因此画布面积为 $(-1-(-1))\times(2-(-1))=0$。

样例输出仅表示一种可能的答案，并不表示该样例输出恰好对应标准程序的输出。

提示

本题输入、输出量较大，建议使用较快的输入输出方式，例如关闭 cin 与 cout 的流同步。