#1515. 苏老师的路灯修建
-
ID: 1515
Type: Default
1000ms
256MiB
Tried: 2
Accepted: 1
Difficulty: 10
Uploaded By:
sulaoshi
Tags> 苏老师的路灯修建
说明
苏老师所在的城市最近要统一修建一批路灯，来装饰城市。
城市里一共有 $n$ 个路口，这 $n$ 个路口由 $n - 1$ 条道路相连。
而市长对于路灯的设置有一些自己的想法：
1. 如果两个相邻的路口用同一种路灯，会显得城市很单调
2. 如果两个间接相邻的路口用同一种路灯（两个能够直连到同一路口的路口被认为是间接相邻的路口），会显得城市很难看
现在市长非常头疼，他不知道到底要订几种不同的路灯，现在苏老师自告奋勇的希望帮市长解决问题
结果发现解决不了，于是只能求助于你，请你帮帮他。
输入格式
输入的第一行包含一个整数 $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 33Statistics
Related
In following contests: