作为香港中文大学（深圳）的学生，小 B 第一次进入教学楼时迷路了（因为 TB 在 TC 上面，而 TC 在 TD 上面）。多年后，小 B 成了新校园教学楼的设计师，现在他正在设计教学楼的剖面图。

新的教学楼将有 $2n$ 个教学区，编号为 $1$ 到 $2n$。设计的占地长度为 $2n$ 个单位，建筑高度限制为 $n + 1$ 个单位，这意味着剖面图可以看作一个 $(n + 1) \times (2n)$ 的网格。每个网格点必须包含一个 $0$ 到 $2n$ 之间的数字。$1 \sim 2n$ 表示该位置的教学区编号，而 $0$ 表示该位置不属于任何教学区。在剖面图中，每个教学区必须是四连通（4-connected）*的。

设 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列网格点处的教学区编号。如果存在 $i, j$（$1 \le i \le n$，$1 \le j \le 2n$）使得 $a_{i,j} = x$ 且 $a_{i+1,j} = y$，我们称教学区 $x$ 在教学区 $y$ 上方（$x \neq y$）。

为了结构上的清晰与美观，小 B 确定了 $(2n - 1)$ 个关系。第 $i$ 个关系的格式为“教学区 $x_i$ 在教学区 $y_i$ 上方”。如果我们添加一条从 $x_i$ 到 $y_i$ 的有向边，这 $2n$ 个教学区恰好形成一棵以教学区 $1$ 为根的向下的树（downward tree）**。

现在，你需要设计一个合法的剖面图（即为每个网格单元分配一个教学区编号），使得该剖面图对应的有向图与小 B 给出的树完全相同。（也就是说，必须满足小 B 指定的关系，而小 B 未指定的关系绝不能满足。）

请输出任意一种合法的填充方案，或报告无解。

*四连通（4-connected）：如果一个网格点集合中的任意两个点都可以通过一条同样属于该集合的相邻（上、下、左、右）网格点序列相连，则称该集合是四连通的。

**向下的树（Downward tree）：一棵具有指定根的有向树，其中每条边都从父亲指向孩子（即从较上层指向较下层）。在本题中，给定的 $2n-1$ 个“教学区 $x_i$ 在教学区 $y_i$ 上方”的关系对应有向边 $x_i \to y_i$，且这些边形成一棵以 $1$ 为根的向下的树。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 500$），表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$（$1 \le n \le 500$）。

接下来 $2n - 1$ 行，每行包含两个整数 $x_i, y_i$，表示一个关系。保证输入形成一棵以 $1$ 为根的向下的树。

还保证 $\sum n \le 2000$。

输出格式

对于每个测试用例：

• 如果存在合法解，输出 $n + 1$ 行，每行包含 $2n$ 个整数，表示构造的方案。如果存在多个解，输出其中任意一个。
• 如果无解，输出单行，包含字符串 No solution。

样例

输入样例 1

1
2
1 2
1 3
2 4

输出样例 1

2 1 1 1
2 2 2 3
4 4 0 3