На фабрике 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.

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

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

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

N
A_0 A_1 ... A_{N-2}
B_0 B_1 ... B_{N-2}
C_0 C_1 ... C_{N-2}

Для $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 другим возможным возвращаемым значением, помимо [1, 0, 0], является [0, 1, 0].

При втором вызове Query изделие со стола $0$ перевозится на стол $2$ по конвейеру $0$ и останавливается там. Обратите внимание, что это изделие не будет перевезено на стол $1$ по конвейеру $1$.

Обратите внимание, что эти входные данные не удовлетворяют ограничениям ни одной подзадачи.

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