Є $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$. Інакше ваша програма отримає вердикт «Неправильна відповідь [1]».

• Функцію Query не можна викликати більше ніж $100\,000$ разів. Інакше ваша програма отримає вердикт «Неправильна відповідь [2]».

• void Bridge(int u, int v)

За допомогою цієї функції ви повідомляєте, як острови з'єднані мостами.

• Параметри u і v означають, що острови $u$ і $v$ безпосередньо з'єднані мостом.
• Якщо умова $0 \le u < v \le N - 1$ не виконується, ваша програма отримає вердикт «Неправильна відповідь [3]».
• Якщо острови $u$ і $v$ не з'єднані безпосередньо мостом, ваша програма отримає вердикт «Неправильна відповідь [4]».
• Якщо функцію Bridge викликано з тими самими параметрами u і v кілька разів, ваша програма отримає вердикт «Неправильна відповідь [5]».
• Оскільки є $N - 1$ мостів, функцію Bridge потрібно викликати рівно $N - 1$ разів. Якщо на момент завершення виконання функції Solve кількість викликів функції Bridge не дорівнює $N - 1$, ваша програма отримає вердикт «Неправильна відповідь [6]».

Важливі зауваження

• Ваша програма може реалізовувати інші функції для внутрішнього використання або використовувати глобальні змінні.
• Ваша програма не повинна використовувати стандартний ввід і стандартний вивід. Ваша програма не повинна жодним способом обмінюватися даними з іншими файлами. Однак ваша програма може виводити налагоджувальну інформацію до стандартного потоку помилок.

Компіляція та тестовий запуск

З вебсторінки змагання можна завантажити архів, що містить приклад модуля оцінювання для перевірки вашої програми. Архів також містить приклад вихідного файлу вашої програми.

Приклад модуля оцінювання міститься у файлі 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 [1].

Якщо ваша програма отримує кілька типів вердикту «Неправильна відповідь», приклад модуля оцінювання повідомляє лише один із них.

Обмеження

Означення $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, якщо ваша програма правильно працює на всіх тестах, ваш бал визначається так, де $X$ — максимальна кількість викликів функції Query в одному тесті.

   • 49 балів, якщо $40\,000 < X \le 100\,000$, та
   • 71 бал, якщо $X \le 40\,000$.

Приклад взаємодії

Нижче наведено приклад вхідних даних для прикладу модуля оцінювання та відповідні виклики функцій.

Вхідні дані 1

5
0 1
0 2
1 3
1 4

Приклад викликів