Minimum First Visit Time Sum in a Tree

You are given a tree with n nodes. Initially, you may choose any node as your starting point. At each unit of time, you can move from your current node to any one of its adjacent nodes. As you traverse the tree, record the time when each node is first visited.

Your task is to choose a starting node and an optimal route in order to minimize the sum of the first visit times of all nodes. Mathematically, if you denote by \(t_u\) the time at which node \(u\) is visited for the first time, you want to minimize:

[ S = \sum_{u=1}^{n} t_u ]

Hint: Note that if you start at a given node \(v\) and choose a route that always moves towards an unvisited node when possible, the first visit time for any node \(u\) is simply the distance \(d(v,u)\) from \(v\) to \(u\) in the tree. Therefore, the problem reduces to finding the node \(v\) such that \(\sum_{u=1}^{n} d(v, u)\) is minimized.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of nodes in the tree.

The following n-1 lines each contain two integers u and v (1 ≤ u, v ≤ n), which indicate that there is an edge between nodes u and v in the tree.

outputFormat

Output a single integer: the minimum possible sum of the first visit times over all nodes.

sample

3
1 2
2 3

2