当前没有测试数据。

E - 来自星星的礼物

评分：$475$ 分

问题描述

如果一个图有 $(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$ 按升序排序，用空格隔开并输出。

对于此问题，我们可以证明解是唯一的。

6
1 2
2 3
3 4
4 5
5 6

2 2

两个等级为 $2$ 的星图可以组成 $T$，如下图所示：

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