CourseBench引流计划

这也是CourseBench引流计划的一部分。

题目描述

上海铁科的教学评价网站CourseBench即将堂堂复活。为了能让更多学生体验到CourseBench，谷米莱莉娅的朋友，CourseBench开发扛把子之一的克拉丽芙决定进行引流。

具体来说，现在上海铁科共有$n$个CourseBench的潜在客户，为了简便将他们编号为$1,2,\dots,n$。他们之间的认识关系形成了一个$n-1$条边的无向连通图。克拉丽芙的目标是让这$n$个同学都使用上CourseBench，但是她又不希望在每个同学身上都花巨大的精力来安利，因为她还得催Pusher push他们。

于是她通过缜密的观察，发现这些同学之间其实可以互相安利：对于任何一名同学来说，只要他/她认识的同学中有不少于$\frac 12$的同学正在使用CourseBench，那么他/她也会开始使用CourseBench。现在她想知道，她最开始需要安利至少多少名同学，就可以让这$n$个同学都开始使用CourseBench。

输入格式

输入第一行包含一个整数$n$。

接下来$n-1$行，每行两个整数$x,y$，表示编号为$x$的同学和编号为$y$的同学互相认识。

输出格式

输出第一行包含一个整数，表示至少安利的同学数量。

样例

3
1 2
2 3

1

6
1 2
1 3
2 4
2 5
3 6

1

数据范围

对于$30\%$的数据，$n\le 10$​。

对于$50\%$的数据，$n\le 10^3$。

对于另外$20\%$的数据，保证图是一条链。

对于$100\%$的数据，$n\le 10^6$。