该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小 Q 困在了一个迷宫里！

这个迷宫形似一棵树，有 $n$ 个节点， $n-1$ 条边将节点连通。$1$ 号点是迷宫的出口。

小 Q 制定了如下的逃跑路线：每次选择从已经到达过的节点出发，一步能够到达的、未到达过节点中，编号最小的点作为下一个到达的点。若到达 $1$ 号点，则逃跑结束。

现在小 Q 想请你数一数，将每一个节点作为起点，需要经过除起点外的多少个节点，才能到达节点 $1$ 呢？

Format

Input

第一行一个正整数 $n$，表示节点数量。

接下来 $n-1$ 行，每行两个数 $x,y$，表示一条树边。

Output

输出一行 $n$ 个数，第 $i$ 个数表示将 $i$ 节点作为起点时的答案。

Samples

5
1 3
3 4
3 5
4 2

0 3 1 3 2

Hints

$2:2 \rightarrow 4\rightarrow 3\rightarrow 1$。

$3:3 \rightarrow 1$。

$4:4 \rightarrow 2\rightarrow 3\rightarrow 1$。

$5:5 \rightarrow 3\rightarrow 1$。

Limitation

对于 $20\%$ 的数据，保证 $1 \le n \le 100$。

对于 $40\%$ 的数据，保证 $1 \le n \le 1000$。

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$。

时空限制：1000ms/256MiB。