У Микро имеется дерево с n вершинами. Микро может выполнять на дереве следующую операцию. Он может выбрать вершину и удалить ее вместе со всем поддеревом (корнем которого является выбранная вершина) из текущего места, после чего прикрепить поддерево в качестве сына к любой другой вершине. Микро определил функцию f(x) на дереве как минимальное количество операций, необходимых для того чтобы из вершин дерева сделать прямую цепь, если дерево подвешено за корень x. Сейчас Микро хочет найти минимум среди всех f(i), где 1 ≤ i ≤ n.

Входные данные

Первая строка содержит количество вершин n (1 ≤ n ≤ 16) в дереве. Следующие n − 1 строк содержат по два целых числа x и y (1 ≤ x, y ≤ n), указывающих на существование ребра между вершинами x и y.

Выходные данные

Вывести требуемый ответ.