种草

题目描述

到了一年中 Farmer John 在他的草地里种草的时间了。 整个农场由 $N$ 块草地组成，方便起见编号为 $1…N$，由 $N−1$ 条双向的小路连接，每块草地都可以经过一些小路到达其他所有的草地。 Farmer John 当然可以在每块草地里种不同种类的草，但是他想要使得使用的草的种类数最小，因为他用的草的种类数越多，他就需要负担更高的花费。 不幸的是，他的奶牛们对选择农场上的草表现得十分苛刻。 如果两块相邻（由一条小路直接相连）的草地种了同一种草，或者即使是两块接近相邻（均可由一条小路直接连向同一块草地）的草地，那么奶牛们就会抱怨她们进餐的选择不够多样。 Farmer John 能做的只能是抱怨这些奶牛，因为他知道她们不能被满足的时候会制造多大的麻烦。 请帮助 Farmer John 求出他的整个农场所需要的最少的草的种类数。

输入格式

输入的第一行包含 $N$。 以下 $N−1$ 行每行描述了一条小路连接的两块草地。

输出格式

输出 Farmer John 需要使用的最少的草的种类数。

4
1 2
4 3
2 3

3

提示

#### 数据范围与提示 $1≤N≤10^5$ #### 样例解释 在这个简单的例子中， 4 块草地以一条直线的形式相连。 最少需要三种草。例如，Farmer John 可以用草 A，B 和 C 将草地按 A−B−C−A 的方式播种。

来源

童程童美