Farmer John даёт каждой корове телефон для общения. Для связи нужны вышки на $N$ пастбищах ($1 \le N \le 10,000$), пронумерованных $1,\ldots,N$.

Ровно $N-1$ пар соседствуют; любые $A$, $B$ ($1 \le A \le N; 1 \le B \le N; A \ne B$) связаны последовательностью соседних пастбищ от $A$ до $B$. Вышки ставят только на пастбищах, каждая обслуживает своё и все соседние.

Найдите минимум вышек для обслуживания всех пастбищ.

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

Читайте из стандартного ввода.

• Строка 1: целое $N$.
• Строки $2,\ldots,N$: пара соседних пастбищ, целые $A$, $B$ через пробел.

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

Пишите в стандартный вывод.

• Строка 1: целое, минимальное число вышек.

Примеры

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

5
1 3
5 2
4 3
3 5

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

2

Примечание

5 пастбищ: соседствуют 1 и 3, 5 и 2, 4 и 3, 3 и 5. Геометрия такая (или похожая):

               4  2
               |  |
            1--3--5

Вышки можно поставить на 2 и 3 либо 3 и 5.

Автор задачи: Jeffrey Wang, 2007