На заводі JOI Co., Ltd. є $N$ столів, пронумерованих від $0$ до $N-1$. На заводі є $N-1$ стрічкових конвеєрів, пронумерованих від $0$ до $N-2$. Конвеєр $i$ ($0 \le i \le N-2$) з'єднує столи $A_i$ та $B_i$. Він транспортує вироби з одного столу на інший. Проте напрямок транспортування не видно. Якщо не враховувати напрямки конвеєрів, будь-яка пара столів з'єднана послідовністю конвеєрів.

IOI-kun — директор заводу. Оскільки він забув напрямок транспортування кожного конвеєра, він кілька разів виконає таку послідовність операцій.

1. Обирає деякі конвеєри та змінює напрямки транспортування обраних конвеєрів на протилежні.
2. Обирає деякі столи та кладе по одному виробу на кожен обраний стіл.

3. Для кожного столу, на який покладено виріб, одночасно відбувається одне з такого.

   • Якщо немає конвеєра, що транспортує вироби з цього столу, нічого не відбувається.
   • Якщо є конвеєри, що транспортують вироби з цього столу, виріб перевозиться одним із них. Виріб зупиняється на кінцевому столі цього конвеєра й більше не рухається.
4. IOI-kun перевіряє для кожного столу, чи є на ньому один або більше виробів. Якщо на столі є вироби, він забирає їх усі.
5. Для кожного конвеєра, напрямок якого було змінено в операції 1, IOI-kun знову змінює напрямок на протилежний. Він стає таким, як був спочатку.

IOI-kun хоче визначити початковий напрямок кожного конвеєра, виконавши цю послідовність операцій не більше ніж 30 разів.

Напишіть програму, яка за інформацією про столи, з'єднані конвеєрами, реалізує стратегію IOI-kun для визначення початкового напрямку кожного конвеєра за не більше ніж 30 виконань цієї послідовності операцій.

Деталі реалізації

Потрібно надіслати один файл.

Цей файл — conveyor.cpp. Він має реалізувати наведену нижче функцію. Програма повинна підключати conveyor.h за допомогою директиви препроцесора #include.

У conveyor.cpp слід реалізувати таку функцію.

void Solve(int N, std::vector<int> A, std::vector<int> B)

Ця функція викликається лише один раз для кожного тесту.

• Параметр N — кількість столів $N$.
• Параметри A, B — масиви довжини $N-1$, що описують столи, з'єднані конвеєрами.

Ваша програма може викликати наведену нижче функцію.

std::vector<int> Query(std::vector<int> x, std::vector<int> y)

За допомогою цієї функції IOI-kun виконує операції на заводі.

• Параметр x — масив довжини $N-1$. Для $0 \le i \le N-2$ IOI-kun змінює напрямок конвеєра $i$ на протилежний, якщо x[i] = 1, і не змінює його, якщо x[i] = 0.
• Параметр y — масив довжини $N$. Для $0 \le j \le N-1$ IOI-kun кладе виріб на стіл $j$, якщо y[j] = 1, і не кладе, якщо y[j] = 0.
• Нехай z — значення, яке повертає ця функція. Це масив довжини $N$. Для $0 \le j \le N-1$ на столі $j$ є один або більше виробів, якщо z[j] = 1, і немає виробів, якщо z[j] = 0.
• Довжина масиву x має дорівнювати $N-1$. Інакше ваша програма отримує вердикт Wrong Answer [1].
• Кожен елемент масиву x має дорівнювати 0 або 1. Інакше ваша програма отримує вердикт Wrong Answer [2].
• Довжина масиву y має дорівнювати $N$. Інакше ваша програма отримує вердикт Wrong Answer [3].
• Кожен елемент масиву y має дорівнювати 0 або 1. Інакше ваша програма отримує вердикт Wrong Answer [4].
• Функцію Query можна викликати не більше ніж 30 разів. Якщо викликати її більше ніж 30 разів, ваша програма отримує вердикт Wrong Answer [5].

void Answer(std::vector<int> a)

За допомогою цієї функції IOI-kun повідомляє початковий напрямок кожного конвеєра.

• Параметр a — масив довжини $N-1$. Для $0 \le i \le N-2$ конвеєр $i$ транспортує вироби з $A_i$ до $B_i$, якщо a[i] = 0, і з $B_i$ до $A_i$, якщо a[i] = 1.
• Довжина масиву a має дорівнювати $N-1$. Інакше ваша програма отримує вердикт Wrong Answer [6].
• Кожен елемент масиву a має дорівнювати 0 або 1. Інакше ваша програма отримує вердикт Wrong Answer [7].
• Якщо IOI-kun повідомляє неправильний напрямок конвеєра, ваша програма отримує вердикт Wrong Answer [8].
• Функцію Answer потрібно викликати рівно один раз. Якщо викликати її більше ніж один раз, ваша програма отримує вердикт Wrong Answer [9]. Якщо після завершення функції Solve функцію Answer не було викликано, ваша програма отримує вердикт Wrong Answer [10].

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

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

Компіляція та пробний запуск

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

Приклад модуля перевірки — файл grader.cpp. Щоб протестувати програму, помістіть grader.cpp, conveyor.cpp, conveyor.h в один каталог і виконайте наведену нижче команду компіляції. Натомість можна запустити compile.sh, який міститься в архіві.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

Якщо компіляція успішна, буде створено виконуваний файл grader.

Зауважте, що справжній модуль перевірки відрізняється від прикладу. Приклад модуля перевірки виконується як один процес, який читає вхідні дані зі стандартного вводу та записує результати в стандартний вивід.

Вхідні дані для прикладу модуля перевірки

Приклад модуля перевірки читає такі дані зі стандартного вводу.

$$ \begin{array}{l} N \\ A_0\ A_1\ \cdots\ A_{N-2} \\ B_0\ B_1\ \cdots\ B_{N-2} \\ C_0\ C_1\ \cdots\ C_{N-2} \end{array} $$

Для $0 \le i \le N-2$ маємо $C_i=0$, якщо конвеєр $i$ транспортує вироби зі столу $A_i$ на стіл $B_i$. Інакше маємо $C_i=1$.

Вихідні дані прикладу модуля перевірки

Приклад модуля перевірки виводить у стандартний вивід таку інформацію (лапки наведено для ясності).

• Якщо програма отримала правильний вердикт, модуль повідомляє кількість викликів функції Query, наприклад Accepted: 22.
• Якщо програма отримала будь-який вердикт Wrong Answer, приклад модуля перевірки виводить його тип, наприклад Wrong Answer [4].

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

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

./grader 2023

Зауваження щодо оцінювання

Для деяких тестів справжній модуль перевірки є адаптивним. Це означає, що він не має фіксованої відповіді спочатку та відповідає залежно від попередніх викликів Query. Гарантується існування принаймні однієї відповіді, яка не суперечить усім відповідям модуля перевірки.

Обмеження

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

• $0 \le A_i \le N-1$ ($0 \le i \le N-2$).
• $0 \le B_i \le N-1$ ($0 \le i \le N-2$).
• Якщо не враховувати напрямки конвеєрів, будь-яка пара столів з'єднана послідовністю конвеєрів.

Підзадачі

1. (1 бал) $N=2$.
2. (14 балів) $N=30$.
3. (10 балів) $N=100\,000$, $A_i=i$ ($0 \le i \le N-2$), $B_i=i+1$ ($0 \le i \le N-2$).
4. (75 балів) $N=100\,000$.

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

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

Вхідні дані 1

3
0 2
2 1
1 0

Для першого виклику Query іншим можливим значенням, що повертається, є [0, 1, 0], окрім [1, 0, 0].

Для другого виклику Query виріб зі столу $0$ транспортується на стіл $2$ конвеєром $0$ і там зупиняється. Зауважте, що цей виріб не буде перевезено на стіл $1$ конвеєром $1$.

Зауважте, що цей приклад вхідних даних не задовольняє обмеження жодної підзадачі.

Серед файлів, доступних на вебсторінці змагання, sample-02.txt задовольняє обмеження підзадачі 1, а sample-03.txt — підзадачі 2.