Description

There is a village with $n$ villagers, connected by $n-1$ paths so that all $n$ homes are connected. Each path has length $1$. The village head wants to hold a meeting at some villager’s home. He wants the sum of distances from all villagers to the meeting place to be minimal. Which villager’s home should be chosen, and what is the minimum total distance? If multiple nodes meet the condition, choose the node with the smallest index.

Input Format

The first line contains an integer $n$, the number of villagers.

The next $n-1$ lines each contain two integers $a$ and $b$, indicating that there is a path between villager $a$ and villager $b$.

Output Format

Output two integers $x$ and $y$ in one line.

Here, $x$ is the villager’s home where the meeting will be held.

$y$ is the minimum possible sum of distances.

4
1 2 
2 3 
3 4 

2 4

Hint

Constraints

For $70\%$ of the testdata, $n \le 10^3$.

For $100\%$ of the testdata, $n \le 5 \times 10^4$.

Translated by ChatGPT 5