이 문제는 인터랙티브 문제입니다.

달콤한 향기가 가득한 이 축제에서, 마지막을 장식할 디저트인 쌍피내를 만드는 과정에 마지막 난관이 찾아왔습니다.

가게에서 가장 인기 있는 디저트인 완벽한 쌍피내를 만들려면 위층의 케이크와 아래층의 푸딩을 완벽하게 융합해야 합니다. 이 신비한 벼룩 왕국에서는 두 층의 디저트 요소가 지닌 에너지가 서로 얽혀 복잡한 도시 네트워크 속에 숨어 있습니다.

가게의 두 베테랑 디저트 장인 dacake8과 dapudding8은 여러분을 시험해 보기로 했습니다. 두 사람은 케이크와 푸딩을 각각 도시 사이의 도로에 숨겨 두었습니다. 두 사람에게 질문하여 여러분이 있는 본점(도시 $1$)과 연결되어 있고 디저트가 숨겨진 도시를 정확히 찾아야만 이 마지막 디저트인 쌍피내를 완성할 수 있습니다!

$n$개의 도시가 있고, 모든 두 도시 사이에는 도로가 있습니다. 케이크는 $n-1$조각이며, $i$번째 조각은 도시 $u_{i,1}$과 도시 $v_{i,1}$을 연결하는 도로에 있습니다. 푸딩도 $n-1$개이며, $i$번째 푸딩은 도시 $u_{i,2}$와 도시 $v_{i,2}$를 연결하는 도로에 있습니다. 케이크가 있는 도로와 푸딩이 있는 도로는 각각 하나의 트리를 이룹니다.

처음에는 케이크와 푸딩의 구체적인 위치를 알지 못합니다. dacake8과 dapudding8에게 다음과 같은 질문을 최대 $\min(1000,\frac{n\times(n-1)}{2})$번 할 수 있습니다.

• dacake8과 dapudding8에게 도시 $u$와 도시 $v$를 질문합니다. 처음에 다중집합 $S$는 비어 있습니다.

  • dacake8은 도시 $u$에서 출발하여 케이크가 있는 도로로 이루어진 경로를 따라 도시 $v$에 도착하고, 지나간 도시의 번호를 다중집합 $S$에 추가합니다.
  • dapudding8은 도시 $u$에서 출발하여 푸딩이 있는 도로로 이루어진 경로를 따라 도시 $v$에 도착하고, 지나간 도시의 번호를 다중집합 $S$에 추가합니다.

• 인터랙터는 다중집합 $S$를 반환합니다.

여러분이 있는 도시는 도시 $1$입니다. 질문을 마친 뒤에는 도시 $1$과 도시 $u$를 연결하는 도로에 한 종류 이상의 디저트가 있는 도시 $u$를 제시해야 합니다.

dacake8과 dapudding8은 여러분을 곤란하게 만들 생각이 없으므로, 케이크와 푸딩의 위치가 질문을 시작하기 전에 이미 정해져 있음을 보장합니다. 즉, 인터랙터는 비적응형입니다.

구현 세부사항

참가자는 main 함수를 구현할 필요가 없으며, 구현해서도 안 됩니다.

참가자는 소스 파일 milk.cpp에 헤더 파일 milk.h를 포함하고, 다음 두 함수를 구현해야 합니다.

void init(int c, int t);

• $c,t$는 각각 서브태스크 번호와 테스트 케이스 수를 나타냅니다. $id=0$이면 해당 테스트 파일은 예제입니다.
• 각 테스트 파일에 대해, 프로그램 실행을 시작할 때 인터랙터가 이 함수를 정확히 한 번 호출합니다.

int find(int c, int n);

• $c,n$은 각각 서브태스크 번호와 도시 수를 나타냅니다.
• 이 함수는 양의 정수 $u$를 반환해야 합니다. 이는 도시 $1$과 도시 $u$를 연결하는 도로에 한 종류 이상의 디저트가 있는 도시 $u$를 제시한다는 뜻입니다.
• 각 테스트 파일에 대해 인터랙터가 이 함수를 정확히 $t$번 호출합니다.

참가자는 다음 함수를 호출하여 질문을 한 번 할 수 있습니다.

std::vector<int>query(int u, int v);

• $u,v$는 제시하는 두 도시 $u$와 $v$를 나타냅니다.
• 참가자는 $1\le u,v\le n$이고 $u\ne v$임을 보장해야 합니다.
• 이 함수는 다중집합 $S$를 반환합니다. 구체적인 의미는 문제 설명을 참고하세요.
• 다중집합 $S$의 크기를 $m$이라고 하면, $1\le S_i\le n$이고 $S_0\le S_1\le \ldots \le S_{m-1}$입니다.
• 인터랙터가 find를 호출할 때마다 이 함수의 호출 횟수가 $1000$을 넘지 않도록 해야 합니다.

프로그램 테스트 방법

milk.cpp, milk.h, 첨부 파일의 grader.cpp를 같은 디렉터리에 놓고 C++17로 컴파일하세요.

g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.in

컴파일하여 얻은 실행 파일 milk에 대해 다음과 같이 동작합니다.

인터랙터 입력의 첫 번째 줄에는 음이 아닌 정수 $id,t$가 주어집니다. 각각 테스트 파일 번호와 테스트 케이스 수를 나타냅니다.

각 테스트 케이스의 첫 번째 줄에는 도시 수를 나타내는 양의 정수 $n$이 주어집니다. $2\sim n$번째 줄에는 각각 두 양의 정수 $u_{i,1}$, $v_{i,1}$이 주어지고, 이어지는 $n-1$개의 줄에는 각각 두 양의 정수 $u_{i,2}$, $v_{i,2}$가 주어집니다.

find를 $t$번 호출한 결과가 모두 올바르면, 인터랙터는 첫 번째 줄에 Correct!, 두 번째 줄에 Max queries used: Q를 출력합니다. 여기서 $Q$는 모든 테스트 케이스에서 query를 호출한 횟수의 최댓값입니다. 한 번이라도 답이 틀리면 Wrong answer.를 출력합니다. 인터페이스 호출이 유효하지 않으면 표준 오류 스트림에도 오류 이유를 출력합니다.

예제

입력 1

0 3
5
1 5
2 5
2 4
3 5
1 2
1 4
3 4
4 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 7
2 4
3 6
4 6
5 7
5 8
6 8
2
1 2
1 2

출력 1

Correct!
Max queries used: 28

참고

최종 테스트 데이터에는 예제가 포함되지 않는다는 점에 주의하세요.

그림의 빨간색 간선은 두 도시 사이의 도로에 케이크 한 조각이 있음을 나타내며, 파란색 간선은 두 도시 사이의 도로에 푸딩 하나가 있음을 나타냅니다.

첫 번째 테스트 케이스에서 케이크가 있는 도로와 푸딩이 있는 도로로 이루어진 트리의 형태는 다음과 같습니다.

두 번째 테스트 케이스에서 케이크가 있는 도로와 푸딩이 있는 도로로 이루어진 트리의 형태는 다음과 같습니다.

세 번째 테스트 케이스처럼 한 도로에 케이크와 푸딩이 동시에 있을 수도 있습니다.

제한

특수 조건 $\text{A}$: 케이크와 푸딩의 위치는 완전히 무작위로 생성됩니다.

특수 조건 $\text{B}$: 가능한 답이 유일함을 보장합니다.

특수 조건 $\text{C}$: 케이크가 있는 도로와 푸딩이 있는 도로로 이루어진 두 트리를 각각 도시 $1$을 루트로 삼아, 각 도시에서 두 트리 각각의 부모 도시로 향하는 간선을 그으면, 이렇게 얻은 유향 그래프는 DAG를 이룹니다.

특수 조건 $\text{D}$: 케이크가 있는 도로와 푸딩이 있는 도로로 이루어진 두 트리를 각각 도시 $2$를 루트로 삼아, 각 도시에서 두 트리 각각의 부모 도시로 향하는 간선을 그으면, 이렇게 얻은 유향 그래프는 DAG를 이룹니다.

특수 조건 $\text{E}$: 푸딩의 위치는 완전히 무작위로 생성됩니다. 케이크의 위치는 푸딩의 위치에 의존하지 않습니다.

특수 조건 $\text{F}$: 케이크가 있는 도로와 푸딩이 있는 도로로 이루어진 두 트리는 모두 경로이며, 두 경로 모두 도시 $1$을 시작점으로 합니다.

이 문제에서 트리를 무작위로 생성한다는 것은 무작위 Prufer 수열로 생성한다는 뜻입니다.

서브태스크

find가 반환한 답이 올바르지 않거나 query의 인자가 유효하지 않으면, 해당 테스트 파일의 점수 배율은 $0$입니다.

서브태스크 $1,2,3$에서는 질문 횟수가 $\frac{n\times(n-1)}{2}$를 넘으면 해당 테스트 파일의 점수 배율이 $0$이고, 그렇지 않으면 $1$입니다.

서브태스크 $4\sim 15$에서는 모든 테스트 케이스에서 query를 호출한 횟수의 최댓값을 $Q$라고 합니다. 점수 배율 $f(Q)$는 다음 표에 따라 계산합니다.

테스트 파일의 최종 점수는 해당 테스트 파일의 배점에 점수 배율을 곱한 값이며, UOJ의 실수 점수 규칙에 따라 소수점 아래 세 자리까지 표시합니다.

시간 제한: $20\ \mathrm{s}$.

메모리 제한: $512\ \mathrm{MiB}$.