题目描述

对于 $k \geq 2$，满足以下条件、有 $k + 1$ 个顶点和 $k$ 条边的图，称为 $k$ 级星图：

• 存在一个顶点，它通过边与其他 $k$ 个顶点各连接一次。
• 不存在其他边。

高桥最初拥有由若干个星图组成的图。然后，他重复执行以下操作，直到图中所有顶点连通：

• 选图中的两个顶点。这两个顶点必须度数为 1，且原本不连通。在这两个顶点间添加一条边。

之后，高桥随意给操作结束后得到的图的顶点编号为 $1$ 到 $N$。这个图是一棵树，记为 $T$。$T$ 有 $N - 1$ 条边，第 $i$ 条边连接 $u_i$ 和 $v_i$。

后来高桥忘记了最初星图的数量和等级。请根据 $T$ 的信息，求出最初星图的数量和等级。

输入格式

第一行输入一个整数N， 接下来输入N-1条边

输出格式

设高桥最初有 ( M ) 个星图，等级为 ( L = (L_1, L_2, \ldots, L_M) )。将 ( L ) 升序排序后，用空格分隔输出。

本题保证解唯一确定。

6
1 2
2 3
3 4
4 5
5 6

2 2

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$ 个顶点的树
• 输入均为整数