Эта задача является интерактивной.

В этот праздник, наполненный сладкими ароматами, приготовление завершающего десерта — молочного пудинга с двойной плёнкой — столкнулось с последним препятствием.

Этот десерт — самый популярный в магазине, и для его идеального приготовления необходимо безупречно соединить верхний слой торта с нижним слоем пудинга. В этом волшебном королевстве блох энергии двух слоёв десерта переплетаются и скрываются в сложной сети городов.

Два опытных мастера десертов из магазина, 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$. После завершения запросов вам нужно указать город $u$, такой что на дороге, соединяющей города $1$ и $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$, указывающее город $u$, такой что на дороге, соединяющей города $1$ и $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}$.

Если ответы всех $t$ вызовов find верны, библиотека взаимодействия выводит в первой строке 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$ является началом каждой из них.

В этой задаче случайная генерация дерева определяется с помощью случайной последовательности Прюфера.

Подзадачи

Если ответ, возвращённый find, неверен или параметры query некорректны, коэффициент начисления баллов за данный тест равен $0$.

Для подзадач $1,2,3$, если количество запросов превышает $\frac{n\times(n-1)}{2}$, коэффициент начисления баллов за данный тест равен $0$; иначе он равен $1$.

Для подзадач $4\sim 15$ пусть $Q$ обозначает максимальное количество вызовов query среди всех наборов входных данных. Коэффициент начисления баллов $f(Q)$ вычисляется по следующей таблице:

Итоговый балл за тест равен произведению стоимости теста в баллах и коэффициента начисления баллов, с сохранением трёх знаков после запятой согласно правилам UOJ для вещественных баллов.

Ограничение времени: $20\ \mathrm{s}$.

Ограничение памяти: $512\ \mathrm{MiB}$.