You are given a tree consisting of $n$ vertices, numbered from $1$ to $n$. Each of the $n - 1$ edges is associated with two non-negative integers $x$ and $y$.

Consider a permutation$^{\text{∗}}$ $p$ of the integers $1$ through $n$, where $p_i$ represents the value assigned to vertex $i$.

For an edge $(u, v)$, such that $u \lt v$ with associated values $x$ and $y$, its contribution is defined as follows: $$ \begin{cases} x & \text{if } p_u \gt p_v, \\ y & \text{otherwise.} \end{cases} $$

The value of the permutation is the sum of the contributions from all edges.

Your task is to find any permutation $p$ that maximizes this total value.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

Each of the next $n - 1$ lines contains four integers $u$, $v$, $x$, and $y$ ($1 \le u \lt v \le n$, $1 \le x, y \le 10^9$) — describing an edge between vertices $u$ and $v$ with associated values $x$ and $y$. It is guarranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, you must output a permutation $p$ of the integers $1$ through $n$ that maximizes the total value as defined in the problem. If there are multiple answers, you can print any of them.

Note

In the first test case:

Consider the permutation $p = [3, 2, 1]$. Its value is $5 = 2 + 3$. Here's why:

• Since $p_1 \gt p_2$, the first edge contributes $+2$.
• Since $p_2 \gt p_3$, the second edge contributes $+3$.

The values of some other permutations are as follows:

• $p = [1, 2, 3]$ has value $1 + 2 = 3$.
• $p = [1, 3, 2]$ has value $1 + 3 = 4$.
• $p = [3, 1, 2]$ has value $2 + 2 = 4$.

In the second test case:

The value of $p = [2, 3, 5, 4, 1]$ is $3 + 2 + 7 + 100 = 112$. Another possible correct answer is $p = [2, 3, 4, 5, 1]$.