E. Tree with Small Distancestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an undirected tree consisting of n vertices. An undirected tree is a connected undirected graph with n - 1 edges.Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex 1 to any other vertex is at most 2. Note that you are not allowed to add loops and multiple edges.InputThe first line contains one integer n (2 \le n \le 2 \cdot 10^5) — the number of vertices in the tree.The following n - 1 lines contain edges: edge i is given as a pair of vertices u_i, v_i (1 \le u_i, v_i \le n). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.OutputPrint a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex 1 to any other vertex at most 2. Note that you are not allowed to add loops and multiple edges.ExamplesInput71 22 32 44 54 65 7Output2Input71 21 32 42 53 61 7Output0Input71 22 33 43 53 63 7Output1NoteThe tree corresponding to the first example:  The answer is 2, some of the possible answers are the following: [(1, 5), (1, 6)], [(1, 4), (1, 7)], [(1, 6), (1, 7)].The tree corresponding to the second example:  The answer is 0.The tree corresponding to the third example:  The answer is 1, only one possible way to reach it is to add the edge (1, 3).
Input71 22 32 44 54 65 7
Output2
['dp', 'graphs', 'greedy', '*2100']