You are given an undirected tree consisting of n vertices. An undirected tree is a connected 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 vertex 1 to any other vertex is at most 2. Note that you are not allowed to add loops or multiple edges.
The first line contains one integer n(2≤n≤2⋅105) — the number of vertices in the tree.
The next n−1 lines describe the edges: the i-th edge is specified as a pair of vertices ui,vi(1≤ui,vi≤n). It is guaranteed that the given graph is a tree. It is guaranteed that there are no loops or multiple edges among the given edges.
Print a single integer — the minimum number of edges that need to be added in order to ensure that the length of the shortest path from vertex 1 to any other vertex does not exceed 2. Note that you cannot add loops or multiple edges.