Історія з багатьма кінцівками#3288
Ви програміст, який захоплюється бішоджо іграми (піджанр симуляторів побачень). Вчора вийшла гра під назвою "I * C * P * C!", і вона щойно потрапила до вас. У цій грі є кілька кінцівок. Коли ви завершите всі ці кінцівки, ви зможете отримати спеціальну фігурку головної героїні, Сакуї. Тож, ви хочете якнайшвидше почати грати! Але давайте трохи заспокоїмося і подумаємо, як завершити всі кінцівки за найкоротший час.
Ви маєте особливу здатність, яка дозволяє вам знати структуру точок розгалуження в іграх. Завдяки цій здатності, ви дізналися, що всі точки розгалуження в цій грі полягають у виборі між двома варіантами: "Так" або "Ні". Як тільки вибрано інший варіант, розгалужені історії ведуть до різних кінцівок і більше не зливаються, як у бінарному дереві. Ви також помітили, що для проходження гри від однієї точки розгалуження до іншої або до кінцівки потрібно рівно одну хвилину. Крім того, можна припустити, що повернення до початку гри ("скидання") і гра від початку до першої точки розгалуження займає незначний час.
Гра має додаткову функцію під назвою "Швидке збереження", яка може значно скоротити час гри для завершення. Ця функція дозволяє записати точку, де ви зараз граєте, і повернутися туди в будь-який час пізніше. Ви можете записувати будь-яку кількість разів, але можете зберігати лише останню записану точку. Тобто, коли ви використовуєте Швидке збереження, ви перезаписуєте попередній запис. Якщо ви хочете повернутися до перезаписаної точки, вам доведеться знову грати гру з початку.
Отже, давайте оцінимо, скільки часу знадобиться для завершення всіх кінцівок за найкоротший час.
Перший рядок вхідних даних містить одне ціле число (2 \leq N \leq 500{,}000), яке позначає кількість кінцівок у цій грі. Наступні N-1 рядків описують точки розгалуження. -й рядок описує точку розгалуження з ID номером і містить два цілі числа Yes_i і No_i (i+1 \leq Yes_i, No_i \leq N), які позначають ID номери наступних точок розгалуження, коли ви вибираєте "Так" або "Ні" відповідно. Yes_i = N означає, що ви можете досягти кінцівки, якщо виберете "Так", і так само для No_i. Точка розгалуження з ID є першою точкою розгалуження. Точки розгалуження з ID від до (включно) з'являються рівно один раз у Yes_i і No_i.
Виведіть найкоротший час в одному рядку.
Приклад 1