close


C. Max Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
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
Output
3 2 1 
2 3 5 4 1 
1 5 2 3 4
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]$$$.