一颗等级为 $k$ 的星形礼物由 $k+1$ 个顶点组成：其中一个顶点是中心，其余 $k$ 个顶点是叶子，中心与每个叶子之间各有一条边，并且 $k\ge2$。

小婷老师先准备了若干颗顶点互不重合的星形礼物。随后，她反复从当前尚未连通的两个部分中，各选择一个度数为 $1$ 的顶点，用一条新边把它们连接起来，直到全部顶点形成一棵树。最后，她把所有顶点任意编号为 $1$ 到 $N$。

现在小婷老师忘记了最初准备了多少颗星形礼物，也忘记了每颗礼物的等级。请根据最终得到的树，恢复每颗星形礼物的等级，并按从小到大的顺序输出。题目保证答案唯一。

输入格式

第一行输入一个整数 $N$，表示最终树的顶点数量。

接下来 $N-1$ 行，每行输入两个整数 $u_i$ 和 $v_i$，表示顶点 $u_i$ 与顶点 $v_i$ 之间有一条边。

输出格式

在一行中按从小到大的顺序输出所有星形礼物的等级，相邻整数之间用一个空格分隔。

7
7 1
6 1
3 1
5 1
1 4
1 2

6

16
14 3
4 1
2 8
1 6
7 5
11 2
3 13
2 10
7 2
2 9
1 5
15 3
12 3
8 12
3 16

3 5 5

7
5 1
7 1
6 1
4 1
1 3
2 1

6

数据范围与约定

• $3\le N\le2\times10^5$
• 保证输入树可由题面过程构造