题目描述

最近兴起了一股淘金热，$Rikka$也想参加，现在$Rikka$为了到达挖矿地点，必须帮助$Flysky$解决这个问题，给定$n$个城市，给$n-1$条连接这些城市的路，从某一座城市出发，询问在不走回头路的情况下，最多能经过多少不同的城市。
注： 两个版本只有数据范围不同。 数据保证， 给定一个连通图， 不存在重边， 自环。

输入格式

第一行给出一个正整数 $n (1 ≤ n ≤ 2000)$， 接下来 $n - 1$行， 给出两个城市的 ID $a$， $b$， 表示两个城市有一条路相连$（1 ≤ a ≤ n）$， $（1 ≤ b ≤ n）$

输出格式

输出一个数， 表示最大经过城市的数量

样例

3 
1 2
2 3

3