3. Taiga Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a tree, or an undirected connected graph with no cycles, with $$$n$$$ vertices and $$$n - 1$$$ edges. Vertex 1 is the root.

You define a "leaf vertex" to be a vertex on the tree, other than the root, that is adjacent to exactly one branch vertex.

You also define a "branch vertex" to be a vertex on the tree other than the root, that is adjacent to exactly two other vertices, and adjacent to at least one leaf vertex.

You define a tree to be more of a "taiga tree" the more branch vertices that it has. Given a tree, figure out how many branch vertices it has.

Input

The first line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 10^5)$$$: the number of vertices on the tree.

The next $$$n - 1$$$ lines each contain two space-separated integers, each representing an edge on the tree.

Output

Output a single positive integer: the number of branch vertices on the tree, as defined above.

Scoring

Full problem: 15 points

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

Here is a visual representation of the first example case (the branch vertices are circled):