405 - 树的直径

通过次数

34

提交次数

57

时间限制 : 1 秒
内存限制 : 128 MB

给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径,即直径是一个数值概念,也可代指一条路径。

树的直径通常有两种求法,时间复杂度均为O(n)。

现在有一颗树,树根编号为1,顶点个数为V,边长均为1,求树的直径长度。

输入

第一行输入V,表示这颗树有V个结点。

接下来输入V-1行,每行输入两个整数u,v,表示u和v相连。

输出

输出树的直径的长度。

样例

输入

6
1 2
2 3
5 1
5 4
5 6

输出

4

提示

【数据规模】

对于100%的数据,1≤n≤10000,顶点编号1…n.