题目描述

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

输入描述

输⼊的第⼀⾏包含N 。以下1…N ⾏每⾏描述了⼀条⼩路连接的两块草地。

输出描述

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

Samples

4 
1 2 
4 3
2 3

3

样例解释

在这个简单的例⼦中，4块草地以⼀条直线的形式相连。最少需要三种草。例如，Farmer John可以⽤草A，B和C将 草地按A - B - C -A的⽅式播种。