所有 Berland 城市的经典地铁方案由一组由 n 个通道连接的 n 个车站表示,每个通道恰好连接两个车站并且不穿过任何其他车站。此外,在经典方案中,人们可以沿着通道从任何车站到达任何其他车站。这些通道可用于双向移动。每对车站之间的通道不超过一条。
Berland 数学家最近证明了一个定理,即任何经典方案都有一条环路。只能有一条环路。换句话说,在任何经典方案中,我们都可以找到唯一由车站组成的方案(其中任意两个相邻车站通过通道连接),并且该循环不会多次包含任何车站。
这项发明具有强大的社会影响,因为现在可以根据车站与环路的距离进行比较。例如,一位公民可以说“我住在距环路三段的地方”,另一位公民可以回答“你这个失败者,我住在距环路一段的通道”。互联网上很快就充斥着承诺计算从车站到环路的距离的应用程序(向一个短号码发送短信......)。
贝尔兰政府决定结束这些骚乱并开始控制局势。要求你编写一个程序,可以确定城市地铁方案中每个车站距环路的距离。
输入
第一行包含一个整数n (3 ≤ n ≤ 3000),n是地铁方案中的车站数量(以及同时开出的列车)。然后 n 行包含列车的描述,每行一个。每行包含一对整数 xi, yi (1 ≤ xi, yi ≤ n) 并表示存在从车站 xi 到车站 yi 的通道。这些站以任意顺序从 1 到 n 编号。保证 xi ≠ yi 并且没有一对站点包含多于一个通道。这些通道可用于双向旅行。保证给出的描述代表经典的地铁方案。
输出
打印 n 个数字。数字之间用空格隔开,第i个应等于第i个车站距环路的距离。对于环路车站,请打印数字 0。
示例
输入 #1
4 1 3 4 3 4 2 1 2
输出 #1
0 0 0 0
输入 #2
6 1 2 3 4 6 4 2 3 1 3 3 5
输出 #2
0 0 0 1 1 2