E. Поиск дурака
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует бинарное дерево из $$$n+1$$$ вершин ($$$n$$$ нечетное), с вершинами, помеченными $$$0,1,\ldots,n$$$. На каждой вершине может быть написана не более одной буквы, и изначально на всех вершинах ничего не написано. Корень дерева — это вершина $$$0$$$.

В дереве вершина $$$0$$$ является родителем вершины $$$1$$$, в то время как у всех остальных вершин либо $$$2$$$ ребёнка, либо $$$0$$$.

Боб заблудился в одной из вершин дерева и хочет выбраться из дерева, добравшись до вершины $$$0$$$. Это очень легко для большинства людей с обычным здравым смыслом. Однако, поскольку Боб — дурак, он придумал новый способ обхода дерева, введя «Поиск дурака».

Когда Боб находится на вершине $$$v$$$ ($$$1 \le v \le n$$$), его движение определяется следующим образом:

  • Если вершина $$$v$$$ является листом, Боб всегда движется к родителю $$$v$$$; в противном случае он проверяет следующие условия.
  • Если на вершине $$$v$$$ ничего не написано, Боб пишет 'L' на вершине $$$v$$$ и движется к левому ребенку $$$v$$$;
  • Если на вершине $$$v$$$ написано 'L', Боб перезаписывает её на 'R' и движется к правому ребенку $$$v$$$;
  • Если на вершине $$$v$$$ написано 'R', Боб стирает её и движется к родителю $$$v$$$.

Бобу требуется ровно $$$1$$$ секунда, чтобы перейти к соседней вершине, так что Боб потратит ровно $$$x$$$ секунд на выполнение $$$x$$$ перемещений.

Доказано, что независимо от того, с какой вершины начинает Боб, он может добраться до вершины $$$0$$$ за конечное (хотя и возможно необъяснимо большое) время. Мы не знаем, кто это доказал; конечно, это не мог быть Боб, но это определенно доказано.

Для каждой вершины $$$k=1,2,\ldots,n$$$ определите общее время, необходимое для достижения вершины $$$0$$$, если Боб начал с вершины $$$k$$$, в секундах. Поскольку значения могут быть огромными, вам нужно вычислить их по модулю $$$10^9+7$$$.

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 300\,001$$$, $$$n$$$ нечетное).

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$, обозначающие детей вершины $$$i$$$ ($$$0 \le l_i,r_i \le n$$$).

Для каждой вершины, если $$$l_i=r_i=0$$$, это означает, что у вершины нет детей. В противном случае $$$l_i$$$ и $$$r_i$$$ — это левый и правый дети вершины $$$i$$$.

Гарантируется, что входные данные определяют корректное бинарное дерево, удовлетворяющее условиям, указанным в условии.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$300\,001$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$\tau_1,\tau_2,\ldots,\tau_n$$$, разделенных пробелами.

Здесь $$$\tau_k$$$ обозначает общее время, необходимое для достижения вершины $$$0$$$, если Боб начал с вершины $$$k$$$, по модулю $$$10^9+7$$$.

Пример
Входные данные
3
1
0 0
5
2 3
0 0
4 5
0 0
0 0
7
2 3
4 5
0 0
6 7
0 0
0 0
0 0
Выходные данные
1
9 10 14 15 15
13 22 14 27 23 28 28
Примечание

В первом примере есть только две вершины: вершина $$$0$$$ и вершина $$$1$$$. Бобу требуется всего $$$1$$$ секунда, чтобы добраться до вершины $$$0$$$ из вершины $$$1$$$.

Во втором примере дерево представлено следующим образом.

Бобу требуется $$$14$$$ секунд, чтобы добраться до вершины $$$0$$$ из вершины $$$3$$$. Перемещения следующие:

$$$$$$3 \xrightarrow{\mathtt{L}} 4 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{R}} 5 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{L}} 2 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{R}} 3 \xrightarrow{\mathtt{L}} 4 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{R}} 5 \xrightarrow{\mathtt{X}} 3 \xrightarrow{\mathtt{X}} 1 \xrightarrow{\mathtt{X}} 0$$$$$$

Здесь буквы над стрелками обозначают букву на вершине перед переходом к соседней вершине, где $$$\mathtt{X}$$$ обозначает, что ничего не написано.