C. 最大树值

时间限制： 每测试 $2$ 秒
内存限制： 每测试 $256$ 兆字节

给定一棵由 $n$ 个顶点组成的树，顶点编号从 $1$ 到 $n$。每条边 $(u, v)$ 关联两个非负整数 $x$ 和 $y$。

考虑一个整数 $1$ 到 $n$ 的排列 $p$，其中 $p_i$ 表示赋给顶点 $i$ 的值。

对于一条边 $(u, v)$（满足 $u < v$），其关联值为 $x$ 和 $y$，该边的贡献定义如下：

$$\begin{cases} x, & \text{若 } p_u > p_v, \\[4pt] y, & \text{否则}. \end{cases} $$

排列的值是所有边的贡献之和。

你的任务是找到任意一个使该总值最大化的排列 $p$。

---

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1 \leq t \leq 10^4)$。接下来是每个测试用例的描述。

第一行包含一个整数 $n$ $(2 \leq n \leq 2 \cdot 10^5)$ — 树中顶点的数量。

接下来 $n-1$ 行，每行包含四个整数 $u, v, x, y$ $(1 \leq u < v \leq n,\ 1 \leq x, y \leq 10^9)$ — 描述顶点 $u$ 和 $v$ 之间的一条边，其关联值为 $x$ 和 $y$。保证给定的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

---

输出格式

对于每个测试用例，输出一个整数 $1$ 到 $n$ 的排列 $p$，使得按问题定义的总值最大化。如果存在多个答案，你可以输出任意一个。

---

样例

输入

3
3
1 2 2 1
2 3 3 2
5
1 2 1 3
1 5 2 1
2 4 5 7
2 3 1 100
5
2 5 5 2
3 5 4 6
4 5 1 5
1 5 3 5

输出

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

---

样例解释

第一个测试用例：

考虑排列 $p = [3, 2, 1]$。其值为 $5 = 2 + 3$。原因如下：

• 由于 $p_1 > p_2$，第一条边贡献 $+2$。
• 由于 $p_2 > p_3$，第二条边贡献 $+3$。

其他一些排列的值如下：

• $p = [1, 2, 3]$ 的值为 $1 + 2 = 3$。
• $p = [1, 3, 2]$ 的值为 $1 + 3 = 4$。
• $p = [3, 1, 2]$ 的值为 $2 + 2 = 4$。

第二个测试用例：

$p = [2, 3, 5, 4, 1]$ 的值为 $3 + 2 + 7 + 100 = 112$。另一个可能的正确答案是 $p = [2, 3, 4, 5, 1]$。