Micro is having a tree which is having n nodes. Micro can perform some operations on the tree. In one operation he can select a node and remove it along with the entire subtree rooted at it, from its current position and attach it as child of some other node. He defines a functions f(x) on the tree, as the minimum number of operations needed to be done to make a straight chain of nodes out of the given tree, when the tree is rooted at node x. Now Micro wants to find out the minimum of all the f(i) where 1 ≤ i ≤ n.

Input

First line consists of a single integer denoting n (1 ≤ n ≤ 16). Following n − 1 lines consists of two space separated integers x and y (1 ≤ x, y ≤ n) denoting there is an edge between nodes x and y.

Output

Print the required answer.