В дереве есть $N$ белок, запасающих желуди. (Ботаническое) дубовое дерево также является деревом в теории графов: связный граф с $N$ вершинами, пронумерованными от $1$ до $N$, и $N - 1$ неориентированным ребром. Каждая белка сидит в отдельной вершине дерева, и две белки являются соседями, если их вершины соединены ребром.

В порядке возрастания меток вершин, начиная с белки в вершине $1$, каждая белка крадет по одному желудю у соседней белки, у которой в данный момент больше всего желудей. Если у нескольких соседей одинаковое максимальное количество желудей, белка крадет по одному желудю у каждого из них!

Чтобы ограничить последствия этих разборок, вы хотите распределить желуди между белками так, чтобы каждая белка начинала как минимум с $N$ желудями (чтобы ни у одной белки не закончились желуди из-за краж) и заканчивала с тем же количеством желудей после того, как все $N$ белок закончат красть друг у друга, что и было у них изначально. Можно показать, что такое распределение существует, при котором каждая белка начинает максимум с $2N - 1$ желудями. Найдите любое распределение, удовлетворяющее этим условиям.

Paul Danese, CC BY-SA 4.0, via Wikimedia Commons

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

Первая строка входных данных содержит целое число $N$ ($2 \le N \le 10^5$), количество вершин (и белок).

Каждая из следующих $N - 1$ строк содержит два целых числа $u$ и $v$ ($1 \le u, v \le N, u \neq v$), разделенных пробелом, указывающих на то, что между вершинами $u$ и $v$ существует ребро. Между любой парой вершин существует не более одного ребра, и ребра образуют дерево.

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

Выведите $N$ целых чисел $d_1, d_2, \dots, d_N$, разделенных пробелами, удовлетворяющих условию $N \le d_i \le 2N - 1$, где $d_i$ — количество желудей, которое вы хотите распределить белке в вершине $i$. Ваше решение будет принято, если каждая белка закончит с тем же количеством желудей, с которым она начала, после того как произойдут все $N$ краж. Можно доказать, что такое распределение желудей всегда существует.

Примеры

Примеры 1

5
1 2
1 3
1 4
2 5

6 5 7 7 9

Примеры 2

8
5 4
3 7
8 4
4 7
5 2
1 3
6 4

14 15 10 9 13 14 14 14