← 返回题目列表

AtCoder · abc303_e

H. 来自星星的礼物

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

分数: 475 点

问题陈述

图表 (k+1) 顶点和 k 边缘被称为水平-k\ (k\geq 2) 星标当且仅当:

  • 它有一个相互连接的顶点 k 顶点有一条边,并且没有其他边。

起初,高桥有一个由星星组成的图表。 他重复以下操作,直到图中的每一对顶点都连接起来:

  • 在图形中选择两个顶点。 这里,顶点必须是断开的,并且它们的度数必须都是 1。 添加连接所选两个顶点的边。

然后他任意分配了一个整数 1 通过 N 到该过程后图中的每个顶点。 生成的图是一棵树;我们称之为 T. T 有 (N-1) 边缘, i- 第一个连接 u_i 和 v_i.

高桥现在已经忘记了他最初拥有的星星数量和等级。 找到他们,给定 T.

约束

  • 3\leq N\leq 2\times 10^5
  • 1\leq u_i, v_i\leq N
  • 给定的图是 N- 由问题陈述中的过程获得的顶点树。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

输出

假设高桥最初有 M 星星,其等级为 L=(L_1,L_2,\ldots,L_M)。 排序 L 按升序排列,打印时中间有空格。

我们可以证明这个问题的解是唯一的。


示例输入 1

6
1 2
2 3
3 4
4 5
5 6

示例输出 1

2 2

两级-2 星星产量 T,如下图所示:


示例输入 2

9
3 9
7 8
8 6
4 6
4 1
5 9
7 3
5 2

示例输出 2

2 2 2

示例输入 3

20
8 3
8 18
2 19
8 20
9 17
19 7
8 7
14 12
2 15
14 10
2 13
2 16
2 1
9 5
10 15
14 6
2 4
2 11
5 12

示例输出 3

2 3 4 7