Codeforces Round 135 (Div. 2) |
---|
Закончено |
Страна Древляндия состоит из n городов, некоторые пары из которых соединены односторонними дорогами. Всего в этой стране n - 1 дорога. Известно, что если не обращать внимание на направление дорог, то из любого города можно добраться до любого другого.
Недавно советом старейшин было решено выбрать столицу Древляндии. Конечно, это должен быть один из городов страны. Предполагается, что совет будет заседать в столице и регулярно перемещаться из столицы в другие города (об обратном перемещении пока никто не думает). По этой причине, если город a будет выбран столицей, то все дороги должны быть ориентированы так, что, двигаясь по ним, можно из города a добраться до любого другого города. Для этого, возможно, некоторые дороги придется переориентировать.
Помогите старейшинам выбрать столицу так, что необходимо переориентировать минимальное количество дорог в стране.
В первой строке входных данных записано целое число n (2 ≤ n ≤ 2·105) — количество городов в Древляндии. Следующие n - 1 строк содержат описания дорог, по одной дороге в строке. Дорога описывается парой целых чисел si, ti (1 ≤ si, ti ≤ n; si ≠ ti) — номерами соединяемых дорогой городов, i-ая дорога ориентирована из города si в город ti. Считайте, что города в Древляндии пронумерованы от 1 до n.
В первую строку выведите минимальное количество переориентируемых дорог при оптимальном выборе столицы. Во вторую строку выведите все возможные способы выбрать столицу — последовательность номеров городов в порядке возрастания.
3
2 1
2 3
0
2
4
1 4
2 4
3 4
2
1 2 3
Название |
---|