暂无测试数据。

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

子任务 1：（$10\%$）：$1\leq n\leq 2$。

子任务 2：（$20\%$）：$1\leq n\leq 8$。

子任务 3：（$20\%$）：$1\leq n\leq 400$。

子任务 4：（$30\%$）：$1\leq n\leq 2000$。

子任务 5：（$20\%$）：$1\leq n\leq 2\times 10^5$。

3
1 2
2 3

1

4
1 2
2 3
2 4

0