비버들이 사는 $N$개의 섬이 있으며, $0$부터 $N-1$까지 번호가 매겨져 있다. 이 섬들은 $N-1$개의 양방향 다리로 연결되어 있다. 몇 개의 다리를 이용하면 어떤 두 섬 사이든 이동할 수 있다. 각 섬에는 그 섬에 직접 연결된 다리가 최대 18개 있다. 각 섬에는 한 마리의 비버가 살고 있다.

가끔 몇 마리의 비버가 회의를 열기 위해 한 섬에 모인다. 정확히 세 마리의 비버가 만날 때, 그들은 다음 섬에 모인다:

세 마리의 비버가 모일 때 건너는 다리 개수의 총합을 최소화하는 섬 (그러한 섬은 유일하게 존재한다).

이 섬은 세 마리의 비버 중 한 마리가 사는 섬과 일치할 수도 있음에 유의하라.

당신은 $N$개의 섬이 다리로 어떻게 연결되어 있는지에 관심이 있다. 직접 섬에 가서 확인할 수는 없으므로, 비버들에게 몇 가지 지시를 내리려고 한다. 한 번의 지시는 다음과 같다:

• 세 개의 섬 $u$, $v$, $w$ ($0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, $v \ne w$)를 지정하여, 섬 $u$, $v$, $w$에 사는 비버들이 회의를 열게 한다.
• 그러면 세 마리의 비버가 모이는 섬을 알 수 있다.

당신은 적은 횟수의 지시만으로 섬들이 어떻게 연결되어 있는지 알아내고 싶다.

섬의 개수가 주어졌을 때, 비버들과 소통하여 섬들이 어떻게 연결되어 있는지 알아내는 프로그램을 작성하라.

구현 세부사항

하나의 파일을 제출해야 한다.

파일의 이름은 meetings.cpp이다. 이 파일은 다음 함수를 구현해야 한다. 프로그램은 meetings.h를 포함해야 한다.

• void Solve(int N)

이 함수는 각 테스트 케이스마다 정확히 한 번 호출된다.

• 매개변수 N은 섬의 개수 $N$을 나타낸다.

프로그램은 다음 함수들을 호출할 수 있다.

• int Query(int u, int v, int w)

이 함수는 당신이 지정한 세 섬의 번호에 대해, 그곳에 사는 비버들이 회의를 위해 모이는 섬의 번호를 반환한다.

• 세 섬의 번호 $u$, $v$, $w$를 각각 매개변수 u, v, w로 지정한다. 이들은 $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, $v \ne w$를 만족해야 한다. 그렇지 않으면 프로그램은 Wrong Answer [1]로 판정된다.

• 함수 Query는 $100\,000$번을 초과하여 호출할 수 없다. 그렇지 않으면 프로그램은 Wrong Answer [2]로 판정된다.

• void Bridge(int u, int v)

이 함수를 사용하여 섬들이 다리로 어떻게 연결되어 있는지 답한다.

• 매개변수 u와 v는 섬 $u$와 섬 $v$가 다리로 직접 연결되어 있음을 나타낸다.
• 만약 $0 \le u < v \le N-1$이 성립하지 않으면, 프로그램은 Wrong Answer [3]으로 판정된다.
• 만약 섬 $u$와 섬 $v$가 다리로 직접 연결되어 있지 않으면, 프로그램은 Wrong Answer [4]로 판정된다.
• 만약 동일한 매개변수 u와 v로 함수 Bridge를 여러 번 호출하면, 프로그램은 Wrong Answer [5]로 판정된다.
• 다리가 $N-1$개 있으므로, 함수 Bridge는 정확히 $N-1$번 호출되어야 한다. 함수 Solve의 실행이 끝났을 때 함수 Bridge의 호출 횟수가 $N-1$번이 아니면, 프로그램은 Wrong Answer [6]으로 판정된다.

주의사항

• 프로그램에서 내부적인 용도로 다른 함수를 구현하거나 전역 변수를 사용할 수 있다.
• 프로그램은 표준 입력과 표준 출력을 사용해서는 안 된다. 프로그램은 어떠한 방법으로도 다른 파일과 통신해서는 안 된다. 단, 표준 에러(standard error)로 디버깅 정보를 출력할 수는 있다.

컴파일 및 테스트 실행

프로그램을 테스트하기 위한 샘플 그레이더가 포함된 압축 파일을 대회 웹페이지에서 다운로드할 수 있다. 이 압축 파일에는 프로그램의 샘플 소스 파일도 포함되어 있다.

샘플 그레이더는 grader.cpp 파일이다. 프로그램을 테스트하려면 grader.cpp, meetings.cpp, meetings.h를 같은 디렉터리에 두고 다음 명령어를 실행하여 프로그램을 컴파일하라.

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

컴파일에 성공하면 실행 파일 grader가 생성된다.

실제 채점 프로그램은 샘플 그레이더와 다르다는 점에 유의하라. 샘플 그레이더는 단일 프로세스로 실행되며, 표준 입력에서 입력 데이터를 읽고 표준 출력으로 결과를 출력한다.

샘플 그레이더의 입력

샘플 그레이더는 표준 입력으로부터 다음 데이터를 읽어들인다.

$$ \begin{array}{ll} N & \\ A_0 & B_0 \\ \vdots & \\ A_{N-2} & B_{N-2} \end{array} $$

$A_i$와 $B_i$ ($0 \le i \le N-2$)는 섬 $A_i$와 섬 $B_i$가 다리로 직접 연결되어 있음을 나타낸다.

샘플 그레이더의 출력

프로그램이 정상적으로 종료되면, 샘플 그레이더는 표준 출력으로 다음 정보를 출력한다 (따옴표는 명확성을 위한 것이다).

• 프로그램이 정답으로 판정되면, 함수 Query의 호출 횟수를 “Accepted: 100”과 같이 출력한다.
• 프로그램이 오답(Wrong Answer)으로 판정되면, 그 종류를 “Wrong Answer [1]”과 같이 출력한다.

프로그램이 여러 종류의 Wrong Answer에 해당하는 경우, 샘플 그레이더는 그중 하나만 보고한다.

제한

$A_i$와 $B_i$의 정의는 “샘플 그레이더의 입력” 섹션을 참고하라.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• 몇 개의 다리를 이용하면 어떤 두 섬 사이든 이동할 수 있다.
• 각 섬에는 그 섬에 직접 연결된 다리가 최대 18개 있다.

서브태스크

1. (7점) $N \le 7$.
2. (10점) $N \le 50$.
3. (12점) $N \le 300$.

4. (71점) 추가적인 제한 조건이 없다.

5. 서브태스크 1, 2, 3의 경우, 프로그램이 해당 서브태스크의 모든 테스트 케이스에 대해 정답이면 만점을 받는다.

6. 서브태스크 4의 경우, 프로그램이 모든 테스트 케이스에 대해 정답이면, 한 테스트 케이스에서 함수 Query를 호출한 최대 횟수를 $X$라고 할 때 점수는 다음과 같다:

   • $40\,000 < X \le 100\,000$이면 49점,
   • $X \le 40\,000$이면 71점.

인터랙션 예제

다음은 샘플 그레이더의 예제 입력과 그에 대응하는 함수 호출이다.

입력 1

5
0 1
0 2
1 3
1 4

예제 호출