eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Збалансуй-но!

Збалансуй-но!

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Лідеру команди "Відбій" на День Народження подарували підвішене бінарне дерево. Проте, йому не сподобалось, що дерево було незбалансованим. Тепер він хоче видалити мінімальну кількість вершин у дереві, щоы воно стало збалансованим. Перед тим, як видалити вершину з дерева, він зобов'язаний видалити усі вершини з її піддерева.

Нагадаємо, що дерево є збалансованим тоді і лише тоді, коли висота його лівого і правого піддерев відрізняються на 1 (висота порожнього рівна нулю, а висота дерева з однієї вершини - одиниці). Коренем дерева є вершина 1.

Вхідні дані

У першому рядку вхідного файлу задано ціле число n - кількість вершин у дереві (1n1111). У наступних n рядках задано по два цілих числа left_i та right_i - номери лівого та правого сина вершини відповідно, або 0, якщо цього сина не існує.

Вихідні дані

У єдиному рядку вихідного файлу виведіть одне число - шукану мінімальну кількість вершин, що видаляються.

Приклад

Вхідні дані #1
6
2 3
0 0
4 5
0 6
0 0
0 0
Вихідні дані #1
1