Мікро і дерево

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

Вхідні дані

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

Вихідні дані

Виведіть потрібну відповідь.

Приклади