Есть $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

Вызовы функций