分数: 1200 点
问题陈述
高桥的办公室有 N 房间。每个房间都有一个ID 1 to N。 还有 N-1 走廊,以及 i第走廊连接房间 a_i 和房间 b_i。 众所周知,我们可以仅使用这些走廊在任意两个房间之间移动。
高桥在其中一间房间里迷路了。让这个房间成为 r。 他决定回到自己的房间,Room 1,通过以下方式重复行驶:
- 前往与已访问过但尚未访问过的房间相邻的房间中 ID 最小的房间。
让 c_r 是返回房间所需的行程次数 1。 查找全部 c_2,c_3,...,c_N。 注意,一次旅行无论经过多少条走廊,都算一次旅行。
约束
- 2 \leq N \leq 2\times 10^5
- 1 \leq a_i,b_i \leq N
- a_i \neq b_i
- 作为输入给出的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
:
a_{N-1} b_{N-1}
输出
打印 c_r 对于每个 r,格式如下:
c_2 c_3 ... c_N
样本输入 1
6 1 5 5 6 6 2 6 3 6 4
示例输出 1
5 5 5 1 5
例如,如果高桥在房间里迷路了 2,他的行程如下:
- 前往房间 6.
- 前往房间 3.
- 前往房间 4.
- 前往房间 5.
- 前往房间 1.
示例输入 2
6 1 2 2 3 3 4 4 5 5 6
示例输出 2
1 2 3 4 5
示例输入 3
10 1 5 5 6 6 10 6 4 10 3 10 8 8 2 4 7 4 9
示例输出 3
7 5 3 1 3 4 7 4 5