C. Максимальное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Каждому из $$$n - 1$$$ рёбер назначены два целых неотрицательных числа $$$x$$$ и $$$y$$$.

Рассмотрим перестановку$$$^{\text{∗}}$$$ $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$, где $$$p_i$$$ обозначает значение, присвоенное вершине $$$i$$$.

Для ребра $$$(u, v)$$$, где $$$u \lt v$$$, которому назначены числа $$$x$$$ и $$$y$$$, его вклад определяется следующим образом: $$$$$$ \begin{cases} x & \text{если } p_u \gt p_v, \\ y & \text{иначе.} \end{cases} $$$$$$

Значение перестановки — это сумма вкладов всех рёбер.

Ваша задача — найти любую перестановку $$$p$$$, которая максимизирует эту общую сумму.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Каждая из следующих $$$n - 1$$$ строк содержит четыре целых числа $$$u$$$, $$$v$$$, $$$x$$$ и $$$y$$$ ($$$1 \le u \lt v \le n$$$, $$$1 \le x, y \le 10^9$$$), описывающие ребро между вершинами $$$u$$$ и $$$v$$$ с назначенными значениями $$$x$$$ и $$$y$$$. Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных вы должны вывести перестановку $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$, для которой значение максимально. Если существуют несколько перестановок, выведите любую из них.

Пример
Входные данные
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 \gt p_2$$$, первое ребро вносит $$$+2$$$.
  • Поскольку $$$p_2 \gt 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]$$$.