33840번 - 센트로이드 트리와 복원 스페셜 저지

문제

어떤 정점을 제거했을 때 생기는 서브트리들의 크기 중, 가장 큰 서브트리의 크기를 최소로 만드는 정점을 그 트리의 센트로이드라고 한다. 어떤 트리든 센트로이드는 1ドル$개 또는 2ドル$개 존재하고, 트리의 정점 수가 홀수일 경우 그 트리의 센트로이드는 오직 하나만 존재함을 증명할 수 있다.

다음은 트리 $T$에 대해 센트로이드 트리 $T'$ 을 만드는 과정이다. 초기에 센트로이드 트리 $T'$은 간선이 없는 상태로 시작한다.

1. 현재 트리에서 센트로이드 $C$를 찾아 제거한다.
2. $C$를 제거한 뒤 나뉜 각 서브트리에 대해 센트로이드 $C'$를 구한다.
3. 만약 $C'$의 후보가 여러 개라면, $C$와 가장 가까운 후보를 선택한다. $C$와 가장 가까운 후보는 유일함을 증명할 수 있다.
4. 각 서브트리에 구한 $C'$와 이전 센트로이드 $C$를 연결하는 간선 $\{C,\ C'\}$을 센트로이드 트리 $T'$에 추가한다.
5. 각 서브트리에 대해 1~4 과정을 반복하며, 모든 정점이 제거될 때까지 센트로이드 트리를 확장한다.

크기가 $N$인 트리 $T'$이 주어진다. 이 트리가 어떤 트리 $T$의 센트로이드 트리인 경우, 가능한 원래 트리 $T$를 출력하라. 존재하지 않는다면 -1을 출력하라.

트리 $T$가 존재한다면, 트리 $T$의 센트로이드는 오직 하나만 존재함이 보장된다.

입력

첫 번째 줄에 트리 $T'$의 정점의 수 $N$이 주어진다. $(3 \leq N \leq 99\ 999;$ $N$은 홀수$)$

두 번째 줄부터 $N - 1$개의 줄에 걸쳐 트리 $T'$의 간선 정보가 주어진다. 각 줄은 두 정점 $A,ドル $B$가 공백으로 구분되어 주어지며, 이는 트리 $T'$에서 두 정점 $A$와 $B$를 직접 연결하는 간선이 존재함을 의미한다. $(1 \leq A,ドル $B \leq N)$

출력

가능한 원래 트리 $T$의 간선 정보를 출력한다. 출력은 $N - 1$개의 줄로 이루어져야 하며, 각 줄에 두 정점 $A,ドル $B$를 공백으로 구분하여 출력한다. 이는 트리 $T$에서 두 정점 $A$와 $B$를 직접 연결하는 간선이 존재함을 의미한다. 가능한 트리가 여러 개인 경우, 그 중 임의의 트리를 하나 출력한다. $(1 \leq A, B \leq N)$

만약 가능한 $T$가 존재하지 않는다면 -1을 출력한다.

제한

힌트