← 返回题目列表

Codeforces · 131/D

D. 地铁

中文机器翻译题面 查看原题

所有 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