题目描述

给定一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$，以节点 $1$ 为根。

现在需要对每个节点进行染色，每个节点可以被染成红色、蓝色，或者不染色。

染色方案需要满足：

• 对于树中每一个非叶子节点（即至少有一个子节点的节点）$i$，设其子树（包括节点 $i$ 本身以及它的所有后代节点）中红色节点的数量为 $red_i$，蓝色节点的数量为 $blue_i$，都必须有 $red_i = blue_i$。叶子节点没有该限制条件。

求在所有满足条件的染色方案中，整棵树上红色节点数量的最大值。

输入格式

第一行一个正整数 $n$，表示树的节点数。

接下来 $n-1$ 行，每行两个正整数 $u, v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

输出一个整数，表示最多能有多少个红色节点。

样例

5
1 2
2 3
3 4
2 5

2

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 20$。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \leq u, v \le n$。