题目描述

树镇一年一度的马拉松大赛将要举行了。正如它的名字，树镇由 $n$ 座建筑和 $n-1$ 条街道组成，从任何建筑出发，经过一些街道总可以到达任意其他建筑。

树镇的马拉松大赛不仅比拼选手从起点到终点的跑步耗时，也比拼选手的力气，因为选手需要拉着松树通过某一条街道。主办方并没有确定选手应该在哪条街道上拉着松树跑，但是如果确定了这条街道，主办方将选择包含这条街道的简单路径中最长的一条作为比赛路段。

为了为主办方提供决策依据，你需要计算对于每条街道，包含这条街道的简单路径中最长的一条的长度。一条简单路径的长度被定义为这条路径上包含的街道条数。

输入

第一行一个整数 $n\ (1\le n\le 10^6)$，表示建筑个数。

接下来 $n-1$ 行，每行两个整数 $a_i,b_i\ (1\le a_i,b_i\le n)$，表示一条连接建筑 $a_i$ 和 $b_i$ 的街道。保证输入的边可以形成一棵树。

输出

输出 $n-1$ 行，第 $i$ 行输出一个整数，表示包含第 $i$ 条街道的简单路径中最长一条的长度。

样例

样例输入

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

样例输出

4
4
4
4
3
4
4

样例说明

如包含边 $(4,5)$ 的简单路中，最长的一条为 $\{(2,1),(1,4),(4,5),(5,8)\}$，长度为 $4$，因此输出 $4$。

数据范围

本题共 $20$ 组数据。

对于 $5\%$ 的数据，这棵树形态呈星型，也就是存在 $n-1$ 个度为 $1$ 的节点。

对于另 $5\%$ 的数据，这棵树形态呈链型，也就是存在两个度为 $1$ 的节点，其他节点的度数均为 $2$。

对于另 $20\%$ 的数据，$n\le 10^3$。

对于另 $30\%$ 的数据，$n\le 10^5$。

对于全部数据，$2\le n\le 10^6,1\le a_i,b_i\le n$，保证给出的边可以组成一棵树。