Score : $475$ points

问题描述

具有 $(k+1)$ 个顶点和 $k$ 条边的图被称为级别为-$k$（$k\geq 2$）的星形图，当且仅当：

• 它有一个顶点通过边与其它 $k$ 个顶点中的每一个相连，并且没有其他边。

起初，高桥拥有一个由星形图构成的图。他重复执行以下操作，直到图中每对顶点都相互连接：

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

然后，在该过程结束后，他随意地给图中的每个顶点分配从 $1$ 到 $N$ 的整数。由此得到的图是一棵树；我们称之为 $T$。$T$ 具有 $(N-1)$ 条边，其中第 $i$ 条边连接 $u_i$ 和 $v_i$。

现在，高桥忘记了他最初拥有的星星数量和级别。已知 $T$，请找出这些信息。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:32:01