Tree Destruction

n개의 정점으로 이루어진 가중치 없는 트리가 주어진다. 그런 다음 트리에 다음 연산을 n - 1번 적용한다. 한 번의 연산은 다음 단계로 구성된다:

1. 두 잎을 선택한다;
2. 두 잎 사이의 단순 경로의 길이를 답에 더한다;
3. 선택한 잎 중 하나를 트리에서 제거한다.

연산을 적용하기 전의 초기 답은 0이다. 자명하게도 이러한 연산을 n - 1번 수행한 후에는 트리에 정점 하나만 남는다.

달성할 수 있는 답의 최댓값을 계산하고, 이 답을 달성할 수 있는 연산의 순서를 구성한다!

첫째 줄에 트리의 정점 수를 나타내는 정수 하나 n (2 ≤ n ≤ 2·105)이 주어진다.

다음 n - 1개의 줄에는 트리의 간선이 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) 형식으로 주어진다. 주어진 그래프가 트리임이 보장된다.

첫째 줄에 가능한 답의 최댓값을 나타내는 정수 하나를 출력한다.

다음 n - 1개의 줄에는 연산을 적용하는 순서대로 ai, bi, ci 형식으로 출력한다. 여기서 ai, bi은 현재 연산에서 선택한 잎의 쌍 (1 ≤ ai, bi ≤ n), ci (1 ≤ ci ≤ n, ci = ai or ci = bi)은 현재 연산에서 트리에서 제거하는 선택된 잎이다.

더 잘 이해하려면 예제를 참고한다.