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

题目描述

cyh 所在的城市最近要统一修建一批路灯，来装饰城市。

城市里一共有 $n$ 个路口，这 $n$ 个路口由 $n - 1$ 条道路相连。

而市长对于路灯的设置有一些自己的想法：

1. 如果两个相邻的路口用同一种路灯，会显得城市很单调
2. 如果两个间接相邻的路口用同一种路灯（两个能够直连到同一路口的路口被认为是间接相邻的路口），会显得城市很难看

现在市长非常头疼，他不知道到底要订几种不同的路灯，现在 cyh 自告奋勇的希望帮市长解决问题

结果发现解决不了，于是只能求助于你，请你帮帮他。

输入格式

输入的第一行包含一个整数 $n$，表示路口数量。 接下来 $n - 1$ 行，每行包含两个整数 $x,y$ 表示 $x,y$ 两个路口是直接相连的

输出格式

输出最少需要订购几种不同的路灯

数据范围

对于 $10\%$ 的数据满足：$n \leq 10$

对于 $50\%$ 的数据满足：$n \leq 50000$

对于 $100\%$ 的数据满足：$n \leq 10^5$

样例输入

4
1 2
4 3
2 3

样例输出

3