1942 - 深度最大
Description

给定N个节点,请你找到一个节点,以它为根的时候深度之和最大!

Input

第一行一个整数N,表示节点数量

接下来N-1行,每行两个数字u,v,表示u和v有一条边

Output

输出最大的深度之和

Examples

Input

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

Output

28
Hint

选择7或者8作为根

数据约束:

50%数据,N<=100;

100%数据,N<=500000;

题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 90
通过次数 47