△

$N$개의 정점으로 이루어진 트리가 주어진다. 모든 정점 쌍에 대하여 두 정점 사이 거리의 합이 최소가 되는 트리를 구성한다. 정점에는 $1$부터 $N$까지 번호가 매겨져 있다.

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

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

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

둘째 줄부터 $N-1$개의 줄에 걸쳐 트리를 이루는 간선의 정보를 출력한다. 각 줄에는 간선이 연결하는 두 정점의 번호를 공백을 사이에 두고 출력한다. 조건을 만족하는 트리가 여러 개라면 아무거나 하나 출력한다.