407966: GYM102953 3 Taiga Tree

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

3. Taiga Treetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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 <= n <= 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

ExamplesInput
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):

加入题单

上一题 下一题 算法标签: