Ця задача є інтерактивною.

У це свято, сповнене солодких ароматів, приготування завершального десерту — молока з подвійною плівкою — зіткнулося з останньою перешкодою.

Цей десерт є найпопулярнішим у крамниці. Щоб приготувати ідеальне молоко з подвійною плівкою, потрібно досконало поєднати верхній шар торта з нижнім шаром пудингу. У цьому чарівному королівстві бліх енергії двох десертних складників переплітаються, приховані у складній мережі міст.

Двоє досвідчених майстрів десертів із крамниці — 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}$.