У багатьох місцях Росії взимку йде сніг. У Росії є $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.

Написи на схемі: 降雪情報 — інформація про сніг; 中継サーバ — проміжний сервер; 容量 $L$ ビット — місткість $L$ бітів; 質問ごとに 20 ビットまで — до 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 A[i] < B[i] \le N-1$.

• void Anya(int C[])

  Ця функція викликається $Q$ разів після виклику InitAnya. Вона відповідає вибору послідовності бітів, яку Anya зберігає на проміжному сервері після оновлення інформації про сніг на початку дня.

  • Аргумент C[] — послідовність довжини $N-1$, що описує інформацію про сніг на дорогах. Елемент $C[i]$ ($0 \le i \le N-2$) — ціле число 0 або 1, що описує стан дороги $i$: $C[i]=1$ означає, що на дорозі $i$ йде сніг, а $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 всі біти проміжного сервера обов'язково ініціалізуються нулями. Отже, на момент завершення Anya позиції, які не були записані за допомогою Save, містять 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 A[i] < 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$ послідовно виконуються такі дії:

   • (a) Функція Anya викликається рівно один раз. Це відповідає вибору послідовності бітів для збереження на проміжному сервері після оновлення інформації про сніг на початку дня.
   • (b) Функція Boris викликається $D_i$ разів, де $D_i$ — кількість запитань громадян у день $i$. Аргумент її виклику $j$ ($1 \le j \le D_i$) дорівнює $R_{ij}$ ($1 \le R_{ij} \le N-1$). Якщо повернене значення у виклику $j$ не дорівнює мінімальній кількості доріг, на яких іде сніг, якими необхідно проїхати з міста $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 після виклику Anya з номером $i$ ($1 \le i \le Q$) не отримали вердикт «Неправильна відповідь», у цей момент виводиться один рядок із $D_i$ цілих чисел, розділених пробілами. Число $j$ ($1 \le j \le D_i$) дорівнює значенню, яке повернула Boris для аргументу $R_{ij}$.

Якщо виконувана програма задовольняє кілька умов неправильної відповіді, виводиться лише один із відповідних типів.

Обмеження

Усі вхідні дані задовольняють такі умови:

• $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(...), наведено нижче.