Description

给定一棵n个点的树，你需要增加一条边，使得图中的路径条数尽可能大。

其中本题考虑的路径都是至少经过一条边，且不经过重复点的路径。

Format

Input

第一行包含一个整数n。 接下来的n-1行，每行包含两个整数u,v，代表树中一条边的两个端点。

N<=500000

Output

一行，一个整数，代表最大的路径条数。

Samples

4
1 2
1 3
1 4

11