题目描述

某一天,灰之魔女伊蕾娜来到了芙兰老师所在的国家,但是在与芙兰老师团聚之后不久,伊蕾娜又要踏上她的旅途,与芙兰老师分别了。虽然踏上旅途之后伊蕾娜无法再见到芙兰老师,但是她依然想要在芙兰老师所在的国家待久一些。

芙兰老师所在的国家有 $n$ 个城市(编号为 $1,2,...n$ ), $n$ 个城市之间通过 $n-1$ 条道路相连,伊蕾娜做了一个旅行计划:每一天会选择一个没有游览过的城市居住下来,并且在这天里坐着她的扫帚,优雅地游览一遍居住的城市和相邻的城市(有道路相连的城市)。在第一天,她居住在芙兰老师所在的城市(编号为 $1$ ),并且已经游览过相邻的城市一遍了。并且由于她的扫帚的速度很快,在选择每一天居住的城市时,她能在快速飞到任何一个城市,但是缺点是飞行路途上的城市是无法优雅地游览的,只能在居住下来之后才能开始游览附近和居住的城市。

现在她想要在遵守自己旅行计划的前提下,尽量多的在芙兰老师的国家中停留。你知道她最多停留多少天吗?


输入格式

第 $1$ 行包括一个整数 $n(1 \leq n \leq 10^6)$ ,表示城市的数量。

接下来第 $2$ 到第 $n$ 行,每一行包括两个整数 $u_i,v_i(1\leq u_i,v_i \leq n)$ ,表示城市 $u_i$ 与城市 $v_i$ 相邻。(保证输入是一棵树)


输出格式

输出一个整数,表示伊蕾娜在芙兰老师的国家停留的天数。(伊蕾娜第一天居住在城市1)


样例数据

输入

9
1 2
1 3
1 4
2 5
2 6
2 7
3 8
4 9

输出

6

备注


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务