#3225. 为树之国选首都
为树之国选首都
题目描述
Treeland 国由 座城市组成,某些城市对之间由单向道路连接,全国共有 条道路。已知不考虑道路方向时,从任意城市都能到达其他任意城市。
长老会最近决定选定 Treeland 的首都。首都要求是本国的某座城市。长老会将在首都集合,并定期从首都前往其他城市(现阶段还没人考虑怎么回来)。因此,若选城市 作为首都,就必须把所有道路的方向调整成:沿道路方向,从城市 可以到达其他任何城市。为此可能需要把一些道路反向。
请帮长老们选出首都,使需要反向的道路数量最少。
输入格式
输入的第一行包含整数 (),表示 Treeland 的城市数。接下来 行描述这些道路,每行一条。每条道路用一对整数 (,)描述,即该道路连接的两座城市。第 条道路的方向是从城市 指向城市 。Treeland 的城市编号为 1 到 。
输出格式
第一行输出最优选择首都时需要反向的最少道路数。第二行按递增顺序输出所有可以作为首都的城市编号。
3
2 1
2 3
0
2
4
1 4
2 4
3 4
2
1 2 3