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