← 返回题目列表

AtCoder · tessoku_book_el

B65. 晋升之路艰难

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

配点: 1000 点

問題文

KYOPRO-MASTER有限公司 我们有 N\ (\leq 100000) 员工, 它们的编号最大为1 减去 N 。 为竞争对手公司工作的太郎做了以下事情: 获得 N-1 信息。

i 项目信息:员工 A_i 和员工 B_i 具有直接上级和下级之间的关系。在这里,员工们 目前尚不清楚 A_i 和 按字典顺序比较 B_i 中的哪一个才是老大。

社員 T 是总统和其他 N-1 每个人都是某人 1 编写一个程序来查找每个员工在直接下属时的“级别”。 然而,没有下属的员工的级别是 0 ,有下属的员工的级别等于直接报告的最高级别。 假设它是 1 的总和。

制約

  • 2 \leq N \leq 100000
  • 1 \leq T \leq N
  • 1 \leq A_i \lt B_i \leq N\ (1\leq i\leq N-1)
  • i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
  • 直接上级和下级之间存在满足所有给定条件的关系。 请输出
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N T
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

社員 1,2,\ldots,N 的“类”值,并用空格分隔。


入力例 1

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

出力例 1

3 1 2 1 0 0 0

入力例 2

15 1
1 2
2 3
1 4
1 5
1 6
6 7
2 8
6 9
9 10
10 11
6 12
12 13
13 14
12 15

出力例 2

4 1 0 0 0 3 0 0 2 1 0 2 1 0 0

给定的图表如下所示: 输出