Maximize Sum of Depths

Problem Description

Given a tree with $n$ nodes, find a node to serve as the root such that the sum of the depths of all nodes is maximized. Output that maximum sum of depths.

Note: the depth of the root is $1$.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

The following $(n-1)$ lines each contain two integers $u, v$, indicating an edge connecting $u$ and $v$.

Output Format

Output one positive integer: the maximum sum of depths.

Sample Input

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

Sample Output

28

Constraints

$0 \le n \le 10^6$. That is, an empty tree may exist.

$1 \le u, v \le n$, and the given edges are guaranteed to form a tree.