该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近学习了《树的直径》这节课

课程中，首先定义了 《简单路径》 是不经过重复边或重复点的路径

而 《树的直径》 是树上两点之间的 最长简单路径

现在徐老师已经完成了基础练习

题目会给出一棵包含 $n$ 个结点的树，有 $n - 1$ 条边连接，每条边的长度均为 $1$

而现在徐老师突发奇想，想到了一个很有趣的问题

如果一棵树的直径只有一条，至少需要添加几个结点，才能保证这棵树的直径不唯一？

P.S. 增加结点时，会先指定原树上的一个结点，然后和这个新的结点连接一条长度为 $1$ 的边，所以新加入结点后，依旧是一棵树

输入格式

第一行输入一个整数 $n$ 表示这棵树的结点数量

接下来 $n-1$ 行每行两个整数 $u_i,v_i$ 表示一条边连接了 $u_i,v_i$ 两个结点

输出格式

输出一个整数，表示最少需要增加几个结点才能使得这棵树的直径不唯一

数据范围

存在 $10\%$ 的数据满足：$1\leq n\leq 2$。

存在 $20\%$ 的数据满足：$1\leq n\leq 8$。

存在 $20\%$ 的数据满足：$1\leq n\leq 400$。

存在 $30\%$ 的数据满足：$1\leq n\leq 2000$。

存在 $20\%$ 的数据满足：$1\leq n\leq 2\times 10^5$。

以上数据分组均独立

样例输入1

3
1 2
2 3

样例输出1

1

样例解释1

可以发现添加新的节点后与节点 $2$ 相连便可以使新的树具有两条直径。

样例输入2

4
1 2
2 3
2 4

样例输出2

0

样例解释2

图中已经存在两条直径了：1-2-3 和 1-2-4，因此结果为 $0$。