每年为了庆祝春天的到来，Byteburg 都会举行盛大的 ByteSpring 游行。今年，Byteasar XVI 国王将亲临现场。Byteburg 的街道网络由 $n$ 个交叉路口和 $n-1$ 条双向街道组成，且任意两个交叉路口之间都是连通的。

游行的具体路线尚未确定，但已知游行将从一个交叉路口出发，经过若干条街道，最后在另一个不同的交叉路口结束。为了让游行队伍保持兴致，游行路线经过的每条街道最多只能经过一次。

更重要的是，为了确保游行队伍的安全，所有满足“恰好有一个端点在游行路线上”（包括起点和终点）的街道都必须封闭。你的目标是确定可能需要封闭的街道的最大数量。

输入格式

输入的第一行包含一个整数 $n$ ($n \ge 2$)，表示 Byteburg 的交叉路口数量。交叉路口编号为 $1$ 到 $n$。

接下来的 $n-1$ 行描述了 Byteburg 的街道网络。每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，由空格分隔，表示编号为 $a$ 和 $b$ 的交叉路口之间有一条双向街道。

输出格式

输出一行一个整数，表示为了保障游行安全，最多需要封闭的街道数量。

样例

样例输入 1

8
1 2
2 3
4 2
5 2
6 5
5 7
7 8

样例输出 1

5

说明

如果游行从交叉路口 $2$ 出发，在交叉路口 $7$ 结束，则需要封闭 $5$ 条街道：$(2,1), (2,3), (2,4), (5,6), (7,8)$，其中 $(a, b)$ 表示连接编号为 $a$ 和 $b$ 的交叉路口的街道。

子任务

测试数据分为以下子任务。每个子任务内可能包含多个测试组。