E - A Gift From the Stars Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

以下の条件を満たす k+1 頂点 k 辺のグラフをレベル k\ (k\geq 2) の星と呼びます。

  • ある 1 つの頂点が、他の k 個の頂点と 1 本ずつ辺で結ばれている。それ以外の辺は存在しない。

高橋君は、はじめ何個かの星からなるグラフを持っていました。そして、以下の手続きを全てのグラフの頂点が連結になるまでくり返し行いました。

  • 持っているグラフの頂点から二つの頂点を選ぶ。このとき、選んだ二つの頂点の次数は共に 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 つのレベル 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

Score : 475 points

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