406843: GYM102569 H Tree Painting

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

Description

H. Tree Paintingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a tree with $$$n$$$ vertices and $$$(n-1)$$$ edges. At the beginning its edges and vertices are not painted. You can perform the following operation: choose two vertices in the tree and paint the path between them (all vertices and edges along this path are painted).

What is the minimal number of such operations to paint the whole tree (all edges and all vertices)?

Input

The first line contains the integer $$$n$$$ ($$$2 \le n \le 200000$$$) — the number of vertices in the tree.

Each of the next $$$(n-1)$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — the vertices connected by the $$$i$$$-th edge.

Output

Output one integer — the minimal number of operations to paint the tree.

ExamplesInput
5
1 2
1 3
1 4
1 5
Output
2
Input
5
1 2
2 3
3 4
4 5
Output
1
Input
4
1 2
3 2
4 2
Output
2

加入题单

上一题 下一题 算法标签: