В стране

Бакытжан в категроии Математика, вопрос открыт 02.07.2017 в 11:02

n
n
городов (
n>1000
n>1000
), некоторые пары городов соединены дорогами. Известно, что из каждого города можно попасть в любой другой город, проезжая по нескольким дорогам. Кроме того, дороги не образуют циклов, то есть если выйти из некоторого города по какой-то дороге и далее двигаться так, чтобы не проходить по одной дороге дважды, то невозможно возвратиться в начальный город. Назовем город хорошим, если он соединен дорогой ровно с одним городом. Найдите минимальное количество хороших городов (и минимальное
n
n
, при котором это значение достигается).