센트로이드 트리와 복원

시간 제한1초메모리 제한1024 MB

요약
주어진 트리가 어떤 트리의 센트로이드 트리가 될 수 있는지 판정하고, 가능하면 원래 트리 하나를 복원해 출력한다.
난이도

어려움10점 중 9점

유형
트리, DFS, 구현, 재귀
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

입력

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

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

출력

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

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

예제3

  1. 예제 1

    입력
    7
5 6
2 1
4 2
6 7
4 6
2 3
    예상 출력
    1 2
2 3
3 4
4 5
5 6
6 7

  2. 예제 2

    입력
    7
1 6
2 3
2 4
2 5
4 6
6 7
    예상 출력
    5 2
2 3
2 4
4 1
1 6
6 7

  3. 예제 3

    입력
    7
1 2
2 3
3 4
4 5
5 6
6 7
    예상 출력
    -1