给你一个由 $$$n$$$ 个顶点组成的无向树。无向树是具有 $$$n - 1$$$ 边的连通无向图。
您的任务是添加最少数量的边,使得从顶点 $$$1$$$ 到任何其他顶点的最短路径长度最多为 $$$2$$$。请注意,不允许添加循环和多条边。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
以下 $$$n - 1$$$ 行包含边:边 $$$i$$$ 作为一对顶点 $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) 给出。保证给定的边形成一棵树。保证给定的边中不存在环路和重边。
输出
打印一个整数 - 为了使从顶点 $$$1$$$ 到任何其他顶点的最短距离最多为 $$$2$$$,必须添加的最小边数。请注意,不允许添加循环和多条边。
示例
输入 #1
7 1 2 2 3 2 4 4 5 4 6 5 7
输出 #1
2
输入 #2
7 1 2 1 3 2 4 2 5 3 6 1 7
输出 #2
0
输入 #3
7 1 2 2 3 3 4 3 5 3 6 3 7
输出 #3
1
注意
第一个示例对应的树:答案是 $$$2$$$,一些可能的答案如下:$$$[(1, 5), (1, 6)]$$$, $$$[(1, 4), (1, 7)]$$$, $$$[(1, 6), (1, 7)]$$$。
第二个例子对应的树:答案是$$$0$$$。
第三个例子对应的树:答案是$$$1$$$,只有一种可能的方法是添加边$$$(1, 3)$$$。