406843: GYM102569 H Tree Painting

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)?

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 one integer — the minimal number of operations to paint the tree.

5
1 2
1 3
1 4
1 5

2

5
1 2
2 3
3 4
4 5

1

4
1 2
3 2
4 2

2