Запасний кабель#13117

Запасний кабель

2 секунди

256 мегабайтів

У країні є $n$ міст, з'єднаних $n - 1$ n-1 двосторонніми дорогами. Між будь-якими двома містами існує рівно один простий шлях.

Щоб підвищити надійність дорожньої мережі, вирішили побудувати рівно одну нову дорогу між двома різними містами, які ще не з'єднані безпосередньо.

Після будівництва розглядаються $n - 1$ n-1 незалежних сценаріїв аварії. У $i$ -му сценарії виходить із ладу лише $i$ -та початкова дорога. Усі інші дороги, зокрема нова, залишаються доступними. Перед кожним сценарієм мережа відновлюється.

Збитком від аварії назвемо кількість міст, що не належать найбільшій компоненті зв'язності мережі після видалення відповідної дороги. Якщо всі міста залишаються з'єднаними, збиток дорівнює нулю.

Виберіть нову дорогу так, щоб сума збитків за всіма $n - 1$ n-1 сценаріями була мінімальною. Знайдіть цю мінімальну суму.

Вхідні дані

Перший рядок містить ціле число $n$ ( $3 \leq n \leq 2 \cdot 1 0^{5}$ 3\le n\le 2\cdot10^5) — кількість міст.

Кожен із наступних $n - 1$ n-1 рядків містить два цілих числа $u_{i}, v_{i}$ u_i,v_i ( $1 \leq u_{i}, v_{i} \leq n$ 1\le u_i,v_i\le n, $u_{i} \neq = v_{i}$ u_i\ne v_i) — кінці $i$ -ї початкової дороги.

Гарантується, що початкова мережа доріг є деревом.

Вихідні дані

Виведіть одне ціле число — мінімальну можливу суму збитків після будівництва однієї нової дороги.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі можна побудувати дорогу між містами $1$ та $4$ . Тоді аварія на будь-якій початковій дорозі не порушить зв'язність мережі, тому відповідь дорівнює $0$ .

У другому прикладі можна побудувати дорогу між містами $2$ та $3$ . Аварії на дорогах $(1, 2)$ та $(1, 3)$ не порушать зв'язність, а аварія на дорозі $(1, 4)$ ізолює одне місто. Сума збитків дорівнює $1$ .

У третьому прикладі нова дорога може захистити лише дві початкові дороги. Дві інші аварії ізолюють по одному місту, тому відповідь дорівнює $2$ .

Оцінювання

Підзадача $1$ ( $20$ балів): $n \leq 9$ n\le 9.
Підзадача $2$ ( $40$ балів): $n \leq 100$ n\le 100.
Підзадача $3$ ( $60$ балів): $n \leq 2000$ n\le 2000.
Підзадача $4$ ( $80$ балів): не більш ніж одне місто з'єднане початковими дорогами з понад двома іншими містами.
Підзадача $5$ ( $100$ балів): без додаткових обмежень.