All submissions for this problem are available.
The country Greenland consists of n cities, some pairs of them are connected with unidirectional roads. Overall there are n - 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 business officials has recently decided to choose the trade centre of Greenland. Of course it should be a city of this country. The council is supposed to meet in the trade centre and regularly move from the trade centre to other cities (at this stage nobody is thinking about getting back to the trade centre from these cities). For that reason if city a is chosen a trade centre, then all roads must be oriented so that if we move along them, we can get from city a to any other city. For that some roads may have to be inversed.
Help the officials to choose the trade centre so that they have to inverse the minimum number of roads in the country.
The first line of the input contains an integer T denoting the number of test cases.The description of T test cases follows.
The first line of each test case contains n — the number of cities in Greenland. Next n - 1 lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers si, ti — the numbers of cities, connected by that road. The i-th road is oriented from city si to city ti. You can consider cities in Greenland indexed from 1 to n.
In the first line print the minimum number of roads to be inversed if the trade centre is chosen optimally. In the second line print all possible ways to choose the trade centre — a sequence of indexes of cities in the increasing order.
- 1 ≤ T ≤ 100
- 2 ≤ n ≤ 2*10^5
- 1 ≤ si , ti≤ n, si≠ ti
Input: 2 3 2 1 2 3 4 1 4 2 4 3 4 Output: 0 2 2 1 2 3
|Time Limit:||0.25 - 0.333333 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions