题目描述

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

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

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

• 持っているグラフの頂点から二つの頂点を選ぶ。このとき、選んだ二つの頂点の次数は共に $1$ であり、かつ選んだ二つの頂点は非連結である必要がある。選んだ二つの頂点を結ぶ辺を張る。

その後、高橋君は手続きが終了した後のグラフの頂点に、適当に $1$ から $N$ の番号を付けました。このグラフは木となっており、これを $T$ と呼びます。$T$ には $N-1$ 本の辺があり、 $i$ 番目の辺は $u_i$ と $v_i$ を結んでいました。

その後高橋君は、はじめ持っていた星の個数とレベルを忘れてしまいました。$T$ の情報からはじめ持っていた星の個数とレベルを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋君が持っていた星が $M$ 個であり、星のレベルがそれぞれ $L=(L_1,L_2,\ldots,L_M)$ であったとする。 このとき、$L$ を昇順に並び替え空白区切りで出力せよ。

なお、この問題では常に解が一意に定まることが証明できる。

题目大意

一个具有 $(k+1)$ 个顶点和 $k$ 条边的图被称为一个级别为 $k（k\ge 2）$的菊花图，当且仅当：

• 它有一个顶点与其他 $k$ 个顶点之间通过一条边相连，而其他顶点之间没有边。

起初，我们有一个由多个菊花图组成的图。重复以下操作，直到整个图变为一张连通图：

• 选择图中的两个顶点。其中顶点之间必须是不连通的，并且它们的度数必须都是 $1$。将这两个顶点用一条边连接起来。

然后，在该过程后，他将整数从 $1$ 到 $N$ 随机分配给图中的每个顶点。生成的图是一棵树，我们称其为 $T$。$T$ 有 $(N-1)$ 条边，第 $i$ 条边连接了 $u_i$ 和 $v_i$。

给定 T，从小到大输出一开始的每个菊花图的 $k$。

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$ 頂点の木
• 入力は全て整数

Sample Explanation 1

以下の図のように、$2$ つのレベル $2$ の星から $T$ は得られます。