CF219D.Choosing Capital for Treeland

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The country Treeland consists of nn cities, some pairs of them are connected with unidirectional roads. Overall there are n1n-1 roads in the country. We know that if we don't take the direction of the roads into consideration, we can get from any city to any other one.

The council of the elders has recently decided to choose the capital of Treeland. Of course it should be a city of this country. The council is supposed to meet in the capital and regularly move from the capital to other cities (at this stage nobody is thinking about getting back to the capital from these cities). For that reason if city aa is chosen a capital, then all roads must be oriented so that if we move along them, we can get from city aa to any other city. For that some roads may have to be inversed.

Help the elders to choose the capital so that they have to inverse the minimum number of roads in the country.
特里兰国由 n 座城市组成,其中一些城市之间有 单向公路相连。全国共有 n - 1 条道路。我们知道,如果不考虑道路的方向,我们可以从任何一个城市到达另一个城市。

长老会最近决定选择特雷兰的首都。当然,它应该是这个国家的一个城市。长老会应该在首都举行会议,并定期从首都前往其他城市(现阶段还没有人考虑从这些城市返回首都)。因此,如果选择城市 a 作为首都,那么所有道路的走向都必须是这样的:如果我们沿着这些道路前进,就可以从城市 a 到达任何其他城市。为此,有些道路可能需要倒置。

帮助长老们选择首都,使他们必须反转全国最少的道路。

输入格式

The first input line contains integer nn ( 2<=n<=21052<=n<=2·10^{5} ) — the number of cities in Treeland. Next n1n-1 lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers si,tis_{i},t_{i} ( 1<=si,ti<=n; siti1<=s_{i},t_{i}<=n; s_{i}≠t_{i} ) — the numbers of cities, connected by that road. The ii -th road is oriented from city sis_{i} to city tit_{i} . You can consider cities in Treeland indexed from 1 to nn .
第一行包含整数 n ( 2n21052 ≤ n ≤ 2·10^5 ) - 特雷兰的城市数量。接下来的 n - 1 行包含道路描述,每行一条。每条道路由一对整数 si, ti ( 1 ≤ si, ti ≤ n; si ≠ ti ) 描述--该道路连接的城市数量。第 i 条道路的方向是从城市 si 到城市 ti 。您可以将 Treeland 的城市从 1 索引到 n 。

输出格式

In the first line print the minimum number of roads to be inversed if the capital is chosen optimally. In the second line print all possible ways to choose the capital — a sequence of indexes of cities in the increasing order.
第一行打印如果最优选择首都,需要反转的最小道路数。第二行打印所有可能的首都选择方式--按递增顺序排列的城市索引序列。

输入输出样例

  • 输入#1

    3
    2 1
    2 3
    

    输出#1

    0
    2 
    
  • 输入#2

    4
    1 4
    2 4
    3 4
    

    输出#2

    2
    1 2 3 
    
首页