来自繁星的礼物

题目描述

具有 $(k+1)$ 个顶点和 $k$ 条边的图被称为 level-$k\ (k\geq 2)$ 星形图,当且仅当:

• 它有一个顶点,与其他 $k$ 个顶点各通过一条边相连,且没有其他边。

最初,高桥有一个由若干星形图组成的图。他不断重复以下操作,直到图中任意两个顶点都连通:

• 选择图中的两个顶点。这里,两个顶点必须不连通,且度数都为 $1$。添加一条连接这两个选定顶点的边。

然后,他给操作结束后图中的每个顶点任意分配了从 $1$ 到 $N$ 的整数。得到的图是一棵树,我们称它为 $T$。$T$ 有 $(N-1)$ 条边,其中第 $i$ 条边连接 $u_i$ 和 $v_i$。

高桥现在忘记了他最初有多少个星形图以及它们各自的 level。给定 $T$,求出这些信息。

输入格式

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

N
u_1 v_1
⋮
u_{N-1} v_{N-1}

输出格式

假设高桥最初有 $M$ 个星形图,它们的 level 为 $L=(L_1,L_2,\ldots,L_M)$。

将 $L$ 按升序排序,并用空格分隔输出。

可以证明本题的答案唯一。

样例

6
1 2
2 3
3 4
4 5
5 6

2 2

两个 level-2 星形图组合起来可以得到 $T$。

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

2 2 2

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

2 3 4 7

数据范围

• $3\leq N\leq 2\times 10^5$
• $1\leq u_i, v_i\leq N$
• 给定的图是通过题目所述操作得到的具有 $N$ 个顶点的树。
• 输入中的所有值均为整数。