Avin has two trees which are not connected. He asks you to add an edge between them to make them connected while minimizing the function $\sum_{i=1}^{n} \sum_{j=i+1}^{n} dis(i,j)$, where $dis(i,j)$ represents the number of edges of the path from $i$ to $j$. He is happy with only the function value.
输入解释
The first line contains a number $n \ (2<=n<=100000)$. In each of the following $n-2$ lines, there are two numbers $u$ and $v$, meaning that there is an edge between $u$ and $v$. The input is guaranteed to contain exactly two trees.