蜘蛛社群层级结构

时间限制：1 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

在“蜘蛛社群”中存在一个清晰的层级结构，规定了谁服从于谁。当然，这并不意味着某位蜘蛛侠比其他蜘蛛侠更不重要或更重要，但在执行多元宇宙救援任务时，确保有人负责协调行动参与者是非常重要的。

社群中共有 $n$ 位蜘蛛，其层级结构形成一棵有根树。树的根是编号为 1 的蜘蛛——米格尔·奥哈拉。层级结构由 $n-1$ 条直接上下级关系给出。若蜘蛛 $u$ 与蜘蛛 $v$ 之间存在直接上下级关系，且 $u$ 在层级中比 $v$ 更靠近米格尔，则称 $u$ 是 $v$ 的“导师”，相应地 $v$ 称为 $u$ 的“下属”。

在迈尔斯出现并逃离之后，社群成员分裂为两派，各自对后续行动有不同的看法。我们将这两种看法分别称为 A 和 B。定义社群中的“混乱度”为满足以下条件的无序对 $(u, v)$ 的数量：蜘蛛 $u$ 是蜘蛛 $v$ 的导师（因此 $v$ 是 $u$ 的下属），且 $u$ 持看法 A，$v$ 持看法 B。

米格尔非常想知道他的盟友各自持何种看法，但他没有时间进行调查。请帮助他确定社群中可能的看法分布，已知当前 混乱度达到最大可能值。

输入格式

第一行包含一个整数 $n$ ——“蜘蛛社群”中的蜘蛛侠数量（$1 \le n \le 10^5$）。

接下来 $n-1$ 行，每行两个整数 $a_i$ 和 $b_i$，表示蜘蛛 $a_i$ 与 $b_i$ 之间存在直接上下级关系（$1 \le a_i, b_i \le n$）。注意，不保证 $a_i$ 是 $b_i$ 的导师，也可能是相反关系。

输入保证这些关系构成一棵树。

输出格式

第一行输出两个整数：最大可能的混乱度 $d$，以及持看法 A 的蜘蛛数量 $k$。

第二行输出 $k$ 个互不相同的整数，范围从 $1$ 到 $n$，表示持看法 A 的蜘蛛编号。

如果存在多个可能答案使得 $d$ 最大，输出任意一个。

样例

样例 1

输入

3
1 2
2 3

输出

1 1
2

样例 2

输入

4
1 2
1 3
1 4

输出

3 1
1

样例 3

输入

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

输出

4 2
2 3