C. Братья-Пожиратели Мира
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы, наверное, слышали о двух братьях, мечтающих править миром. Коль скоро все их предыдущие планы провалились, на этот раз они решили сотрудничать друг с другом для того, чтобы править миром.

Как вы знаете, в мире существует n стран. Эти страны связаны n - 1 направленными дорогами. Если не учитывать направлений дорог, то между каждой парой стран в мире существует уникальный путь, проходящий по каждой дороге не более одного раза.

Каждый из братьев хочет установить свое правление в какой-то стране, сделав это, он сможет контролировать страны, до которых можно добраться из его страны по направленным дорогам.

Братья смогут править миром, если найдется не более двух стран, которые они могут выбрать (и установить свои правления в этих странах), таких, что любая другая страна находится под контролем по крайней мере одной из них. Для того, чтобы сделать это возможным, братья хотят, изменить направление минимального количества дорог. Ваша задача — вычислить это минимальное количество дорог.

Входные данные

Первая строка входных данных содержит целое число n (1 ≤ n ≤ 3000). Каждая из последующих n - 1 строк содержит два целых числа, разделенных пробелом, ai и bi (1 ≤ ai, bi ≤ nai ≠ bi), которые означают, что есть дорога из страны ai в страну bi.

Вы можете считать страны пронумерованными от 1 до n. Гарантируется, что если не учитывать направление дорог, то есть уникальный путь между каждой парой стран в мире, проходящий по каждой дороге не более одного раза.

Выходные данные

В единственной строке выходных данных выведите минимальное количество дорог, которым надо поменять направление для того, чтобы братья смогли управлять миром.

Примеры
Входные данные
4
2 1
3 1
4 1
Выходные данные
1
Входные данные
5
2 1
2 3
4 3
4 5
Выходные данные
0