27966번 - △ 스페셜 저지

$N$개의 정점으로 이루어진 트리의 모든 정점 쌍에 대하여, 두 정점 사이의 거리의 합을 최소화하시오. 정점에는 $1$부터 $N$까지 번호가 매겨져 있다.

즉, 정점 $i$와 정점 $j$ 사이의 거리를 $\textrm {dist}(i,\, j)$라 할 때 $\sum_{1 \leq i < j \leq N}^{} \textrm {dist}(i,\, j)$가 최소인 트리를 구성해야 한다.

첫째 줄에 정점의 개수 $N$이 주어진다. $(2\leq N \leq 100\,000)$

첫째 줄에 모든 정점 쌍에 대하여 두 정점 사이 거리의 합의 최솟값을 출력한다.

둘째 줄부터 $N-1$개의 줄에 걸쳐, 트리를 이루는 간선의 정보를 출력한다. 각 줄에 간선이 연결하는 두 정점의 번호를 공백을 사이에 두고 출력한다.

조건을 만족하는 트리가 여럿이라면 아무거나 하나 출력한다.