#P5. 首都的选择
首都的选择
题目描述
Treeland 国有 个城市,有些城市间存在 单向 道路。这个国家一共有 条路。我们知道,如果把边视作双向的,那么从任意城市出发能到达任意城市。
城市的委员会最近决定为 Treeland 国选择一个首都,显然首都会是国中的一个城市。委员会将在首都开会,并经常去其他城市(这里不考虑从其他城市回到首都)。因此,如果城市 被选为首都,那么所有的道路应该被定向,以使得我们能从城市 到达其他城市。所以,有些路可能需要反转方向。
帮助委员会选择首都使得他们需要反转道路的次数最小。
输入格式
第一行有一个整数 (),表示城市的数量。
接下来 行描述道路,每个道路一行,用一对整数 (,)表示该道路连接的两个城市,第 条道路的方向是从城市 到城市 。
你可以认为 Treeland 国的城市被编号为 到 。
输出格式
第一行输出需要反转的道路数量的最小值。第二行输出所有可能的选择首都的方式,你需要以从小到大的顺序输出所有可能的城市编号。
4
1 4
2 4
3 4
2
1 2 3