D. 小途的新树

小途有一棵有 n 个结点的树，边权均为 1。同时，小途并给出如下定义：

简单路径是不经过重复边或重复点的路径。

直径是树上两点之间的最长简单路径。

显然地，在一棵树中，直径可能有很多条。

小途可以在给出的树中新增一个结点，并指定原树的一个结点与其连边，边权依然为 1。显然地，新增结点后得到的图一定为一棵树。

现在你需要求出，对于给定的树，最少需要新增多少个结点才能使得新树至少有两条直径。

第一行一个正整数 n，表示结点数。

接下来 n−1 行，每行两个整数表示一条边连接的两个结点编号。

输出一行，一个整数表示答案。

样例输入 #1

3
1 2
2 3

样例输出 #1

1

样例输入 #2

4
1 2
2 3
2 4

样例输出 #2

0

样例输入 #3

4
1 2 
2 3
3 4

样例输出 #3

1

子任务 1：（10%）：1≤n≤2。

子任务 2：（20%）：1≤n≤8。

子任务 3：（20%）：1≤n≤400。

子任务 4：（30%）：1≤n≤2000。

子任务 5：（20%）：1≤n≤2×10^5。

样例解释1

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

样例解释2

已经存在两条直径了：“1-2-3” 和 “1-2-4”。因此结果为 0。

样例解释3

可以在节点 2 处添加一个节点；也可以在节点 3 处添加一个节点。因此答案为 1。