给你一棵有 $$$n$$$ 个顶点的树。您可以通过以下多步操作修改树的结构:
1. 选择三个顶点 $$$a$$$、$$$b$$$ 和 $$$c$$$,使得 $$$b$$$ 与 $$$a$$$ 和 $$$c$$$ 相邻。
2. 对于除 $$$b$$$ 之外与 $$$a$$$ 相邻的每个顶点 $$$d$$$,删除连接 $$$d$$$ 和 $$$a$$$ 的边,并添加连接 $$$d$$$ 和 $$$c$$$ 的边。
3. 删除连接 $$$a$$$ 和 $$$b$$$ 的边,并添加连接 $$$a$$$ 和 $$$c$$$ 的边。
作为示例,请考虑以下树:
下图说明了当我们对顶点 $$$2$$$、$$$4$$$ 和 $$$5$$$ 应用操作时发生的步骤顺序:
可以证明,每次操作后,得到的图仍然是一棵树。
找出将树转变为星形所需执行的最少操作数。星形树是一棵树,它有一个度数为 $$$n - 1$$$ 的顶点,称为中心,还有 $$$n - 1$$$ 度数为 $$$1$$$ 的顶点。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
以下 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) 表示存在一条连接顶点 $$$u_i$$$ 的边和$$$v_i$$$。保证给定的边形成一棵树。
输出
打印一个整数——将树转变为星形所需的最少操作数。
可以证明,在给定的约束下,总是可以使用最多 $$$10^{18}$$$ 操作将树转换为星形。
示例
输入 #1
6 4 5 2 6 3 2 1 2 2 4
输出 #1
1
输入 #2
4 2 4 4 1 3 4
输出 #2
0
注意
第一个测试用例对应于语句中显示的树。正如我们之前所看到的,通过对顶点 $$$2$$$、$$$4$$$ 和 $$$5$$$ 应用单个操作,我们可以将树转换为以顶点 $$$5$$$ 为中心的星形树。
在第二个测试用例中,给定的树已经是一个中心位于顶点 $$$4$$$ 的星形树,因此无需执行任何操作。