Мультифинальная история
Вы программист, увлеченный играми жанра биседзе (поджанр симуляторов свиданий). Вчера вышла новая игра под названием "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=N означает, что вы можете достичь концовки, выбрав "Да", и аналогично для No_i. Точка ветвления с ID 1 является первой точкой ветвления. Точки ветвления с ID от 2 до N (включительно) встречаются ровно один раз в Yes_i и No_i.
Выходные данные
Выведите минимальное время в одной строке.