도전

트리를 다루는 많은 프로그래밍 대회 문제는 센트로이드 분해로 해결한다. 트리가 주어지면 먼저 센트로이드를 찾는다. 센트로이드란, 트리에서 그 정점을 제거한 뒤 남는 조각들이 모두 원래 트리 정점 수의 절반 이하를 가지는 정점이다. 그런 다음 찾은 센트로이드를 트리에서 제거하고, 남은 각 조각에 대해 이 과정을 재귀적으로 적용한다. 각 조각의 크기는 한 단계마다 적어도 절반으로 줄어들므로, 정점이 n개인 트리에서 단계는 많아야 log2(n) + 1개다. 다시 말해, 임의의 정점에 대해 그 정점을 포함하면서 알고리즘 도중 처리되는 조각은 많아야 log2(n) + 1개다.

다른 참가자가 센트로이드 분해에서 버그를 만들었다는 사실을 알아챘다. 그 참가자는 센트로이드를 찾는 대신 각 단계에서 트리의 중심(center)을 찾는다. 중심이란, 다른 정점까지의 최대 거리를 최소화하는 정점이다. 더 형식적으로, dij를 정점 i와 j 사이의 거리(트리 간선 수)라고 하면, r = mini(maxj(dij))를 트리의 반지름이라 하고, maxj(dkj) = r인 정점 k를 트리의 중심이라 한다.

이 버그 때문에 분해 단계가 log2(n) + 1개보다 많아질 수 있다. 이 풀이에 도전하려면, 이 '중심 분해'가 적어도 ⌊√n⌋개의 단계를 가지는 트리를 정점 수 n개 이하로 만들어야 한다. 더 정확히는, 분해 도중 처리되는 서로 다른 부분집합에 적어도 ⌊√n⌋번 속하는 정점이 하나 이상 있어야 한다.

어떤 단계의 트리에 중심이 여러 개 있으면, 분해는 정점 번호가 가장 작은 중심을 제거할 중심으로 선택한다고 가정할 수 있다.

입력은 한 줄로 이루어지며, 정수 n이 주어진다. 1 ≤ n ≤ 100000.

출력 첫 줄에 트리의 정점 수 m을 출력한다. 1 ≤ m ≤ n. 다음 m − 1개 줄에 트리의 간선을 설명한다. 각 간선은 연결하는 두 정점의 번호로 나타낸다. 정점은 1부터 m까지 번호가 매겨진다.

트리의 정점 중 적어도 하나는, 중심(여러 개면 정점 번호가 가장 작은 것)을 골라 트리에서 제거하고 남은 모든 조각에 이 과정을 재귀적으로 적용하는 과정에서 적어도 ⌊√n⌋개의 서로 다른 조각에 속해야 한다.