시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB554100.000%

문제

An undirected tree is called even if there is no simple path of odd length connecting two of its leaves. In particular, a tree with just one vertex is considered even.

You are given an undirected tree $G$ with vertices numbered from $1$ to $n$. A graph obtained by removing some (possibly none) of the edges of $G$ is called a forest: it consists of one or more disjoint trees. Determine the minimum possible number $k$ such that we can remove $k$ edges of $G$ in such a way that the resulting forest consists only of even trees.

입력

The first line contains one integer $n$ ($1 \le n \le 10^6$).

Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) denoting an edge connecting vertex $u_i$ and vertex $v_i$.

The graph is guaranteed to be a tree.

출력

Output the minimum number of edges $k$ such that we can remove $k$ edges of $G$ in such a way that each tree in the resulting forest is even.

예제 입력 1

4
1 2
2 3
3 4

예제 출력 1

1

예제 입력 2

4
1 2
1 3
1 4

예제 출력 2

0