F. Доминирующие индексы
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано корневое неориентированное дерево, состоящее из $$$n$$$ вершин. Вершина $$$1$$$ является корнем.

Определим массив глубин вершины $$$x$$$, как бесконечную последовательность $$$[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$$$, где $$$d_{x, i}$$$ — это количество вершин $$$y$$$ таких, что выполняются оба следующих условия:

  • $$$x$$$ является предком $$$y$$$;
  • простой путь из $$$x$$$ в $$$y$$$ проходит ровно по $$$i$$$ ребрам.

Доминирующий индекс массива глубин вершины $$$x$$$ (или же просто доминирующий индекс вершины $$$x$$$) — это такой индекс $$$j$$$, что:

  • для каждого $$$k < j$$$, $$$d_{x, k} < d_{x, j}$$$;
  • для каждого $$$k > j$$$, $$$d_{x, k} \le d_{x, j}$$$.

Для каждой вершины дерева вычислите ее доминирующий индекс.

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество вершин в дереве.

Затем следует $$$n - 1$$$ строка, в каждой записаны по два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$). Эта строка задает ребро в дереве.

Гарантируется, что данные ребра образуют дерево.

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

Выведите $$$n$$$ чисел. $$$i$$$-е число должно быть равно доминирующему индексу вершины $$$i$$$.

Примеры
Входные данные
4
1 2
2 3
3 4
Выходные данные
0
0
0
0
Входные данные
4
1 2
1 3
1 4
Выходные данные
1
0
0
0
Входные данные
4
1 2
2 3
2 4
Выходные данные
2
1
0
0