#P5. 首都的选择

首都的选择

题目描述

Treeland 国有 nn 个城市,有些城市间存在 单向 道路。这个国家一共有 n1n - 1 条路。我们知道,如果把边视作双向的,那么从任意城市出发能到达任意城市。

城市的委员会最近决定为 Treeland 国选择一个首都,显然首都会是国中的一个城市。委员会将在首都开会,并经常去其他城市(这里不考虑从其他城市回到首都)。因此,如果城市 aa 被选为首都,那么所有的道路应该被定向,以使得我们能从城市 aa 到达其他城市。所以,有些路可能需要反转方向。

帮助委员会选择首都使得他们需要反转道路的次数最小。

输入格式

第一行有一个整数 nn2n2×1052 \le n \le 2 \times 10^5),表示城市的数量。

接下来 n1n- 1 行描述道路,每个道路一行,用一对整数 si,tis_i,t_i1si,tin1 \le s_i,t_i\le nsitis_i \ne t_i)表示该道路连接的两个城市,第 ii 条道路的方向是从城市 sis_i 到城市 tit_i

你可以认为 Treeland 国的城市被编号为 11nn

输出格式

第一行输出需要反转的道路数量的最小值。第二行输出所有可能的选择首都的方式,你需要以从小到大的顺序输出所有可能的城市编号。

4
1 4
2 4
3 4
2
1 2 3