← 返回题目列表

Codeforces · 219/D

D. 为Treeland选择资本

中文机器翻译题面 查看原题

乡村Treeland由n个城市组成,其中一些城市通过单向道路连接。该国总共有 n - 1 条道路。我们知道,如果不考虑道路的方向,我们可以从任何一个城市到达任何另一个城市。

长老会最近决定选择树地为首都。当然应该是这个国家的一个城市。该委员会应该在首都举行会议,并定期从首都转移到其他城市(现阶段没有人考虑从这些城市返回首都)。因此,如果选择a城市作为首都,那么所有道路都必须定向,以便如果我们沿着它们行驶,我们可以从a城市到达任何其他城市。为此,某些道路可能必须反转。

帮助长辈们选择首都,以便他们必须反转该国最少的道路数量。

输入

第一个输入行包含整数 n (2 ≤ n ≤ 2·105) — Treeland 中的城市数量。接下来的 n - 1 行包含道路的描述,每行一条道路。道路由一对整数 si, ti (1 ≤ si, ti ≤ n; si ≠ ti) 描述 - 由该道路连接的城市数量。第 i 条路从城市 si 延伸至城市 ti。您可以考虑 Treeland 中索引为 1 到 n 的城市。

输出

在第一行中打印如果首都选择最佳则要反转的最少道路数。在第二行中打印选择首都的所有可能方式——一系列按升序排列的城市索引。

示例

输入 #1

3
2 1
2 3

输出 #1

0
2

输入 #2

4
1 4
2 4
3 4

输出 #2

2
1 2 3