Во многих местах России зимой идёт снег. В России есть $N$ городов, пронумерованных от $0$ до $N-1$, и $N-1$ дорог, пронумерованных от $0$ до $N-2$. Дорога $i$ ($0 \le i \le N-2$) соединяет два различных города $A_i,B_i$ ($0 \le A_i < B_i \le N-1$) в обоих направлениях. Между любыми двумя различными городами России можно проехать по некоторым дорогам.

Ситуация со снегопадом на каждой дороге меняется от дня ко дню. В любой день на каждой дороге либо идёт снег, либо нет. В течение одного дня это состояние не меняется.

Anya и Boris работают в транспортном управлении России. Anya занимается управлением дорожной информацией, а Boris отвечает на вопросы граждан. Граждане спрашивают, какое минимальное число дорог, на которых идёт снег, нужно проехать, чтобы добраться из столицы России, города $0$, до некоторого другого города. Обычно, получив вопрос, Boris связывается с Anya и затем отвечает гражданину.

В России состоится мировой чемпионат по программированию продолжительностью $Q$ дней. Ожидается, что во время чемпионата линии связи будут перегружены и Anya и Boris будет трудно общаться напрямую. Поэтому они решили обмениваться информацией следующим образом.

• В начале дня Anya получает сведения о снегопадах за этот день и отправляет данные на промежуточный сервер.
• Получив вопрос гражданина, Boris отвечает на него, взаимодействуя с промежуточным сервером.

Однако на их обмен информацией наложены следующие ограничения.

• Вместимость промежуточного сервера равна $L=1\,000$ бит. Anya может сохранить на нём не более $L$ бит информации.
• В начале дня все данные на промежуточном сервере инициализируются нулями.
• За одно обращение к промежуточному серверу Boris может прочитать один указанный бит.
• Для ответа на каждый вопрос Boris может обратиться к промежуточному серверу не более 20 раз.

Вы знакомы с начальником транспортного управления, и вам поручено разработать стратегии Anya и Boris.

Сведения о снегопадах → Anya → промежуточный сервер вместимостью $L$ бит → Boris; не более 20 бит на каждый вопрос; граждане.

Задание

Напишите программу, реализующую стратегии Anya и Boris, позволяющие правильно отвечать на вопросы граждан.

Детали реализации

Необходимо отправить два файла на одном и том же языке программирования.

Первый файл должен называться Anya.c или Anya.cpp. Он реализует стратегию Anya и должен содержать следующие две подпрограммы. Программа должна подключать Anyalib.h.

• void InitAnya(int N, int A[], int B[])

Эта функция вызывается ровно один раз в каждом тестовом случае.

• Аргумент N задаёт число городов.

• Аргументы A[] и B[] — последовательности длины $N-1$, описывающие соединения дорогами. Элементы A[i] и B[i] ($0 \le i \le N-2$) — целые числа, означающие, что дорога $i$ соединяет города A[i] и B[i] в обоих направлениях. Они удовлетворяют $0 \le \mathrm{A}[i] < \mathrm{B}[i] \le N-1$.

• void Anya(int C[])

После вызова InitAnya эта функция вызывается $Q$ раз. Она соответствует выбору Anya битовой строки, сохраняемой на промежуточном сервере после обновления сведений о снегопадах в начале дня.

• Аргумент C[] — последовательность длины $N-1$, задающая сведения о снегопадах на дорогах. Элемент C[i] ($0 \le i \le N-2$) равен $0$ или $1$ и описывает снегопад на дороге $i$: C[i] = 1 означает, что снег идёт, а C[i] = 0 — что снег не идёт.

Внутри функции Anya можно вызывать следующую функцию.

• void Save(int place, int bit)

Эта функция соответствует сохранению Anya одного бита на промежуточном сервере.

• Аргумент place задаёт позицию для записи бита. Он должен быть целым числом от $0$ до $L-1$. Вызов со значением вне этого диапазона приводит к вердикту «Неверный ответ [1]». Кроме того, в рамках одного вызова Anya нельзя вызывать эту функцию дважды или более с одним и тем же аргументом place. Повторный вызов с тем же аргументом приводит к вердикту «Неверный ответ [2]».
• Аргумент bit — целое число, задающее записываемый бит; оно должно быть равно $0$ или $1$. Вызов с другим значением приводит к вердикту «Неверный ответ [3]».

После вызова Save бит в позиции place на промежуточном сервере равен bit.

Если вызов Save приводит к неверному ответу, программа немедленно завершается.

Непосредственно перед каждым вызовом функции Anya все биты промежуточного сервера обязательно инициализируются нулями. Иными словами, в позициях, в которые не было записи с помощью Save, после завершения Anya находится $0$.

Второй файл должен называться Boris.c или Boris.cpp. Он реализует стратегию Boris и должен содержать следующие две подпрограммы. Программа должна подключать Borislib.h.

• void InitBoris(int N, int A[], int B[])

Эта функция вызывается ровно один раз в каждом тестовом случае.

• Аргумент N задаёт число городов.

• Аргументы A[] и B[] — последовательности длины $N-1$, описывающие соединения дорогами. Элементы A[i] и B[i] ($0 \le i \le N-2$) — целые числа, означающие, что дорога $i$ соединяет города A[i] и B[i] в обоих направлениях. Они удовлетворяют $0 \le \mathrm{A}[i] < \mathrm{B}[i] \le N-1$.

• int Boris(int city)

После вызова InitBoris эта функция вызывается несколько раз. Она соответствует действиям Boris при ответе на вопрос гражданина.

• Аргумент city описывает вопрос гражданина. Это целое число от $1$ до $N-1$. Гражданин спрашивает, какое минимальное число дорог, на которых идёт снег, нужно проехать, чтобы добраться из города $0$ до города city.
• Функция Boris должна вернуть целое число от $0$ до $N-1$ — ответ на вопрос гражданина. Возврат числа вне этого диапазона приводит к вердикту «Неверный ответ [4]». Неправильный ответ приводит к вердикту «Неверный ответ [7]».

Внутри функции Boris можно вызывать следующую функцию.

• int Ask(int place)

Эта функция соответствует чтению Boris одного бита с промежуточного сервера.

• Аргумент place задаёт позицию читаемого бита. Он должен быть целым числом от $0$ до $L-1$. Вызов со значением вне этого диапазона приводит к вердикту «Неверный ответ [5]».

Возвращаемое значение Ask — целое число $0$ или $1$, равное биту в позиции place на промежуточном сервере. В рамках каждого вызова Boris функцию Ask можно вызвать не более 20 раз. Превышение 20 вызовов приводит к вердикту «Неверный ответ [6]».

Если вызов Ask приводит к неверному ответу, программа немедленно завершается.

Процедура проверки

Проверка выполняется следующим образом. При получении неверного ответа программа немедленно завершается.

1. Для передачи дорожной информации по одному разу вызываются InitAnya и InitBoris, именно в таком порядке.

2. Для $i=1,\ldots,Q$ последовательно выполняются следующие действия.

   • Функция Anya вызывается ровно один раз. Это соответствует выбору Anya битовой строки для промежуточного сервера после обновления сведений о снегопадах в начале дня.
   • Функция Boris вызывается $D_i$ раз. $D_i$ — число вопросов граждан в $i$-й день. Аргумент $j$-го вызова ($1 \le j \le D_i$) равен $R_{ij}$ ($1 \le R_{ij} \le N-1$). Если при $j$-м вызове возвращаемое значение Boris не совпадает с минимальным числом заснеженных дорог, необходимых для проезда из города $0$ до города $R_{ij}$, ответ считается неверным.

3. Если ни разу не был получен неверный ответ, решение считается правильным.

Важные замечания

• Время работы и объём памяти измеряются для шагов (1) и (2) раздела «Процедура проверки». При правильном решении на шаге (2) функция Anya вызывается всего $Q$ раз, а Boris — всего $D_1+\cdots+D_Q$ раз.
• Anya и Boris не могут узнать значения $D_1,\ldots,D_Q$.
• Функции Boris не сообщается, в какой момент функция Anya обновила данные, сохранённые на промежуточном сервере.
• Можно реализовывать другие подпрограммы для внутреннего использования и объявлять глобальные переменные. Однако два отправленных файла объединяются с проверяющей программой в один исполняемый файл, поэтому все глобальные переменные и внутренние подпрограммы в каждом файле (кроме InitAnya, Anya, InitBoris, Boris) необходимо объявлять как static, чтобы избежать конфликтов с другими файлами. При проверке программа запускается в двух процессах — на стороне Anya и на стороне Boris, поэтому они не могут совместно использовать глобальные переменные программы.
• Ваше решение не должно каким-либо способом взаимодействовать со стандартным вводом, стандартным выводом или другими файлами.

Компиляция и запуск

Архив, доступный для скачивания на сайте соревнования, содержит пример проверяющей программы для тестирования вашего решения. В архив также включены примеры файлов, которые необходимо отправить.

Пример проверяющей программы состоит из одного файла: grader.c или grader.cpp. Если ваше решение находится в файлах Anya.c и Boris.c либо Anya.cpp и Boris.cpp, для его проверки выполните следующие команды.

• Для C:

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• Для C++:

g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp

При успешной компиляции будет создан исполняемый файл grader.

Обратите внимание, что настоящая проверяющая программа отличается от примера. Пример запускается как один процесс. Он читает входные данные со стандартного ввода и записывает результаты в стандартный вывод.

Обзор примера проверяющей программы

Пример проверяющей программы вызывает функции согласно разделу «Процедура проверки».

Обратите внимание на следующее отличие от настоящей проверяющей программы.

• Пример не проверяет условие «Неверный ответ [7]», а вместо этого выводит возвращаемое значение Boris для каждого вопроса.

Входные данные примера проверяющей программы

Пример проверяющей программы читает следующие данные со стандартного ввода.

• Первая строка содержит целое число $N$ — число городов.
• В $(i+1)$-й строке ($0 \le i \le N-2$) следующих $N-1$ строк записаны целые числа $A_i,B_i$, разделённые пробелом. Они означают, что дорога $i$ соединяет города $A_i$ и $B_i$ в обоих направлениях.
• Следующая строка содержит целое число $Q$. Оно означает, что чемпионат проходит в течение $Q$ дней.
• $i$-я строка ($1 \le i \le Q$) следующих $Q$ строк содержит строку $S_i$ длины $N-1$ и $D_i+1$ целых чисел, разделённых пробелами. Строка $S_i$ описывает снегопады в $i$-й день: если $(j+1)$-й символ слева ($0 \le j \le N-2$) равен 1, на дороге $j$ идёт снег, а если 0 — не идёт. Первое из следующих $D_i+1$ целых чисел равно $D_i$. Затем следуют $D_i$ целых чисел $R_{i1},\ldots,R_{iD_i}$. Они означают, что $j$-й вопрос ($1 \le j \le D_i$) в $i$-й день касается минимального числа заснеженных дорог, необходимых для проезда из города $0$ до города $R_{ij}$.

Выходные данные примера проверяющей программы

Пример проверяющей программы выводит в стандартный вывод следующие сведения (кавычки на самом деле не выводятся).

• Если во время выполнения получен неверный ответ, выводится его тип, например Wrong Answer [1], и выполнение завершается.
• Если ни один из $D_i$ вызовов Boris после $i$-го вызова Anya ($1 \le i \le Q$) не привёл к неверному ответу, в этот момент в одной строке выводятся $D_i$ целых чисел, разделённых пробелами. $j$-е число ($1 \le j \le D_i$) равно возвращаемому значению Boris(Rij).

Если выполняемая программа нарушает несколько условий неверного ответа, выводится лишь один из соответствующих типов.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1+\cdots+D_Q \le 500$.
• Между любыми двумя различными городами можно проехать по некоторым дорогам.

Подзадачи

Подзадача 1 [15 баллов]

• Выполняется $N \le 20$.

Подзадача 2 [5 баллов]

• Выполняется $N \le 100$.

Подзадача 3 [35 баллов]

Выполняются следующие условия.

• $A_i=i$ ($0 \le i \le N-2$).
• $B_i=i+1$ ($0 \le i \le N-2$).

Подзадача 4 [45 баллов]

Дополнительных ограничений нет.

Примеры

Ниже приведены пример входных данных для примера проверяющей программы и соответствующие вызовы функций.

Входные данные 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Пример вызовов подпрограмм

Обратите внимание, что вызовы функций в этом примере не обязательно имеют осмысленное назначение.

При этом аргументы, передаваемые в InitAnya(...), InitBoris(...), а также при первом и втором вызовах Anya(...), имеют следующий вид.