← 返回题目列表

AtCoder · agc029_e

E. 流浪 TKHS

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

分数: 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