Meeting Point in a Village

Given a tree with \(n\) nodes representing houses in a village and \(n-1\) edges each of length 1 connecting them, the task is to determine the meeting point that minimizes the total distance travelled by all villagers. In other words, if a meeting is held at house \(i\), you need to compute \(S(i)=\sum_{j=1}^{n} d(i,j)\), where \(d(i,j)\) is the distance between houses \(i\) and \(j\). If there are multiple houses achieving the minimum sum, choose the one with the smallest index.

Note: The distance between two houses is defined as the number of edges on the unique path connecting them.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of houses in the village.

The following \(n-1\) lines each contain two integers \(u\) and \(v\) denoting an undirected edge (path) between houses \(u\) and \(v\).

outputFormat

Output two integers separated by a space: the house number where the meeting should be held, and the minimal total distance from all houses to this meeting point.

sample

3
1 2
2 3

2 2