Balance it!
The leader of the "Retreat" team received a hanging binary tree as a birthday gift. Unfortunately, he was unhappy because the tree was unbalanced. He now wants to remove the fewest possible nodes to make the tree balanced. Before removing any node, he must first remove all nodes in its subtree.
A tree is considered balanced if the heights of its left and right subtrees differ by at most 1. (The height of an empty tree is zero, and the height of a tree with a single node is one.) The root of the tree is node 1.
Input
The first line of the input contains an integer n, representing the number of nodes in the tree (1 ≤ n ≤ 1111). The following n lines each contain two integers, left_i and right_i, indicating the left and right children of the node, respectively, or 0 if a child does not exist.
Output
Output a single integer on one line: the minimum number of nodes that need to be removed.