P1395 Meeting

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.

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 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.

#### 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