该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小 $\infty$ 想要尝试图染色问题，但是他不会，于是转向了这个问题。

题目描述

给定一棵树（点 $1$ 为根节点），初始所有节点都是白色的。你可以选择一些节点染红并选择一些节点染黑。现在要求对于每个非叶子节点，其子树（包括自己）中红色节点和黑色节点的数量相等。请求出最多染红的节点数量。

输入格式

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

以下 $n-1$ 行，每行两个正整数 $u$，$v$，表示节点 $u$ 与 $v$ 间有一条边。

输出格式

输出一行表示最多染红的节点数量。

4
1 2
1 3
1 4

2

5
1 2
2 3
3 4
4 5

1

见下发文件中 ex_npc3.in

见下发文件中 ex_npc3.out

提示

样例解释 1

你可以选择节点 $1,2$ 染红，节点 $3,4$ 染黑。

样例解释 2

你可以选择节点 $4$ 染红，节点 $5$ 染黑。

样例解释 3

该样例满足 $n\le5\times10^3$。

数据范围

对于 $100\%$ 的数据，$1\le n\le10^5$，$1 \le u, v \le n$。