#3225. 为树之国选首都

为树之国选首都

题目描述

Treeland 国由 nn 座城市组成,某些城市对之间由单向道路连接,全国共有 n−1n-1 条道路。已知不考虑道路方向时,从任意城市都能到达其他任意城市。

长老会最近决定选定 Treeland 的首都。首都要求是本国的某座城市。长老会将在首都集合,并定期从首都前往其他城市(现阶段还没人考虑怎么回来)。因此,若选城市 aa 作为首都,就必须把所有道路的方向调整成:沿道路方向,从城市 aa 可以到达其他任何城市。为此可能需要把一些道路反向。

请帮长老们选出首都,使需要反向的道路数量最少。

输入格式

输入的第一行包含整数 nn(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5),表示 Treeland 的城市数。接下来 n−1n-1 行描述这些道路,每行一条。每条道路用一对整数 si,tis_i, t_i(1≤si,ti≤n1 \le s_i, t_i \le n,si≠tis_i \ne t_i)描述,即该道路连接的两座城市。第 ii 条道路的方向是从城市 sis_i 指向城市 tit_i。Treeland 的城市编号为 1 到 nn。

输出格式

第一行输出最优选择首都时需要反向的最少道路数。第二行按递增顺序输出所有可以作为首都的城市编号。

3
2 1
2 3
0
2
4
1 4
2 4
3 4
2
1 2 3