题目描述

徐老师最近在复习关于树的直径的知识

• 简单路径是不经过重复边或重复点的路径。
• 直径是树上两点之间的最长简单路径。

对于一棵树而言，求直径的方法是：任选一个点 $x$ 出发找到最远点 $u$，这个 $u$ 一定是这棵树直径的一端，然后从 $u$ 出发找到最远点 $v$，那么 $u-v$ 的路径就是这棵树的一条直径

显然一棵树必然有直径，可能只有一条直径，也可能有多条直径（这里我们认为路径上只要有一个点不同，那么这两条路径就是不同的直径）

而徐老师认为有多条直径的树是 有趣 的，而只有一条直径的树则是 单调 的

现在徐老师有一棵有 $n$ 个节点边权全为 $1$ 的树

徐老师可以在现有的树上新增一个节点，然后选择一个已经存在于树上的节点，将这两个节点用一条边权为 $1$ 的边连接（可以重复新增节点）

现在徐老师想知道，他至少需要增加几个节点，才可以使得新的树是一棵 有趣 的树

输入格式

输入第一行包含一个整数 $n$，表示节点数量

接下来 $n - 1$ 行，每行包含两个整数 $u,v$ 表示存在一条连接了 $u$ 和 $v$ 两个节点的边

输入保证是一棵树

输出格式

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

数据范围

对于 $20\%$ 的数据满足 $1 \leq n \leq 2$

对于 $40\%$ 的数据满足 $1 \leq n \leq 8$

对于 $60\%$ 的数据满足 $1 \leq n \leq 400$

对于 $80\%$ 的数据满足 $1 \leq n \leq 2000$

对于 $100\%$ 的数据满足 $1 \leq n \leq 200000, 1 \leq u,v \leq n$

样例输入1

3
1 2
2 3

样例输出1

1

样例解释1

新增一个节点 $4$，连接 $2-4$，即可使得这棵树存在两条直径 $(1-2-3)$ 和 $(1-2-4)$

样例输入2

4
1 2
2 3
2 4

样例输出2

0

样例解释2

图上本身就已经有两条直径了，所以不需要添加新的节点