C. Catch
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A tree is an undirected connected graph with $$$n$$$ nodes and $$$n - 1$$$ edges. A leaf node refers to a node with degree 1, that is, a node connected to only one node.

You are given an unrooted tree, there are hamsters in some nodes of this tree, and your task is to catch all the hamsters. For this, you can place mousetraps at some nodes. If the hamster moves to the node where the mousetrap is placed, it will be caught immediately. Note that in this problem we consider the capacity of the mousetrap to be infinite, that is, the mousetrap at a single node can also hold an infinite number of hamsters.

Every second, each hamster moves to an adjacent vertex. A hamster cannot move along the same edge twice in a row, unless it entered a leaf node from a non-leaf node in the previous step, in which case it can return from the original edge. Find the minimum number of nodes to place mousetraps so that all hamsters will eventually be caught, regardless of their initial positions and escape strategies.

Input

The first line of input contains a positive integer $$$n(1 \leq n \leq 10^5)$$$, representing the number of nodes in the tree.

The following $$$n - 1$$$ lines, each line contains 2 positive integers $$$u, v(1\leq u, v\leq n)$$$, indicating that there is an edge connecting node $$$u$$$ and node $$$v$$$.

Output

Print a positive integer representing the minimum number of nodes on which to place the mousetrap.

Examples
Input
3
1 2
2 3
Output
1
Input
10
2 8
5 10
3 4
1 6
3 9
1 7
4 8
10 8
1 8
Output
2
Note

For the first testcase, you can place a mousetrap at node 2, because every possible route of the hamsters will certainly include node 2.