103034: [Atcoder]ABC303 E - A Gift From the Stars

Problem Statement

A graph with $(k+1)$ vertices and $k$ edges is called a level-$k\ (k\geq 2)$ star if and only if:

• it has a vertex that is connected to each of the other $k$ vertices with an edge, and there are no other edges.

At first, Takahashi had a graph consisting of stars. He repeated the following operation until every pair of vertices in the graph was connected:

• choose two vertices in the graph. Here, the vertices must be disconnected, and their degrees must be both $1$. Add an edge that connects the chosen two vertices.

He then arbitrarily assigned an integer from $1$ through $N$ to each of the vertices in the graph after the procedure. The resulting graph is a tree; we call it $T$. $T$ has $(N-1)$ edges, the $i$-th of which connects $u_i$ and $v_i$.

Takahashi has now forgotten the number and levels of the stars that he initially had. Find them, given $T$.

Constraints

• $3\leq N\leq 2\times 10^5$
• $1\leq u_i, v_i\leq N$
• The given graph is an $N$-vertex tree obtained by the procedure in the problem statement.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Suppose that Takahashi initially had $M$ stars, whose levels were $L=(L_1,L_2,\ldots,L_M)$. Sort $L$ in ascending order, and print them with spaces in between.

We can prove that the solution is unique in this problem.

Sample Input 1

6
1 2
2 3
3 4
4 5
5 6

Sample Output 1

2 2

Two level-$2$ stars yield $T$, as the following figure shows:

Sample Input 2

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

Sample Output 2

2 2 2

Sample Input 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

Sample Output 3

2 3 4 7

问题描述

如果仅满足以下条件，则称一个具有$(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