题目描述

伏地魔的黑暗势力控制了魔法部与霍格沃茨魔法学校之后，哈利与罗恩、赫敏不得不逃亡在外，隐形遁迹。为了完成校长邓布利多的遗命，一直在暗中寻机销毁伏地魔魂器的哈利，意外地获悉如果他们能够拥有传说中的三件死亡圣器，伏地魔将必死无疑。

在凤凰社成员的帮助下，哈利一行人重新掌控了霍格沃茨。然而此举激怒了伏地魔，他很快率领大批食死徒和黑暗生物向霍格沃茨进军。麦格教授紧急疏散了霍格沃茨的学生，并开始了守卫霍格沃茨的战斗。

霍格沃茨魔法学校的主要建筑共有 $n$ 处，我们编号为 $1$ 到 $n$，这些建筑间由魔法道路连接，整体呈树状分布，即任意两个建筑间有且仅有一条路径相连（路径可以是一条或多条道路组成）。霍格沃茨历经多年风雨，每个建筑自身有许多保护魔法，比如“石墩触动咒”、“降敌陷阱咒”、“统统加护咒”等，只需有人前往施用咒语即能保卫建筑。

现在，伏地魔大军已经到达 $1$ 号建筑——学校大门，凤凰社成员也已经在大门迎战，并且已经启用了大门的保护魔法。然而伏地魔大军势力壮大，保护魔法只能延缓大军的进攻锋芒，他们仍能用一个小时攻克一个建筑，随后整个大军便随机前往与之相邻的另一个建筑（兵贵神速，大军移动过程不需要时间；兵法无常，他们有可能前往已经攻克的建筑）。

目前除了 $1$ 号建筑，其他建筑的保护魔法都尚未被启用，凤凰社决定派出一些成员去其他建筑施用咒语来启动保护魔法。每个凤凰社成员可以瞬间达到任意一个建筑，并用一个小时完成对该建筑保护魔法的启用，之后可以再前往其他的建筑。他们的任务是，保证不论伏地魔大军如何行动，大军所到建筑的保护魔法都已经启用。为了集中更多力量直接打击伏地魔大军，凤凰社希望派出施用咒语的成员数尽可能少。

请你计算，至少需要派出多少位成员。

注：

• 伏地魔大军到达 $1$ 号建筑开始攻击的同时，凤凰社派出成员去其他建筑施咒。

• 当大军攻克某个建筑后，凤凰社成员可以在知道大军下一个小时去哪个建筑的情况下，再决定他们去哪些建筑施咒。这个过程也不需要时间。

• 已经启用过保护魔法的建筑无需再施咒，即便大军攻克该建筑以后某个时候又回到这个建筑，大军也会在这个建筑持续攻击一个小时后再离开。

输入格式

第一行一个整数 $n$，表示建筑的数量。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示建筑 $u$ 和建筑 $v$ 之间有一条魔法道路。

输出格式

一行一个整数，表示最少需要派出施用咒语的成员数。

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

3

提示

数据范围

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$。