题目背景

不要 $\texttt{\#include "conveyer.h"}$。请使用 $\texttt{C++\,20}$ 提交。

提交前请将以下内容粘贴到代码前面：

#include <vector>

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

std::vector<int> Query(std::vector<int> x, std::vector<int> y);
void Answer(std::vector<int> a);

题目描述

在 JOI 有限公司的工厂里，有 $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 会确认每张桌子上是否有产品。如果有产品在桌子上，IOI-kun 会把它们全部拿走。
5. 对于每个在操作 1 中改变了方向的皮带输送机，IOI-kun 都会将其方向恢复到原来的方向。IOI-kun 希望通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

请编写一个程序，根据皮带输送机之间的连接表，实现 IOI-kun 的策略，以通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

实现细节

你需要实现一份 C++ 程序，提交时不需要包含 conveyor.h。

你应该实现以下函数。

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

该函数仅在每个测试用例中被调用一次：

• 参数 $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$，如果 $x_i = 1$，IOI-kun 将反转第 $i$ 个传送带的方向，否则不反转该传送带的方向。
• 参数 $y$ 是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $y_j = 1$，IOI-kun 将在第 $j$ 个桌子上放置一个产品，否则不会在该桌子上放置产品。
• 设 $z$ 是该函数的返回值。它是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $z_j = 1$，则第 $j$ 个桌子上有产品，如果 $z_j = 0$，则第 $j$ 个桌子上没有产品。
• 数组 $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$，如果 $a_i = 0$，则输送带 $i$ 将产品从 $A_i$ 运输到 $B_i$，如果 $a_i = 1$，则将产品从 $B_i$ 运输到 $A_i$。
• 数组 $a$ 的长度必须等于 $N - 1$。如果条件不满足，您的程序将被评为 Wrong Answer[6]。
• 数组 $a$ 中的每个元素都必须为 $0$ 或 $1$。如果条件不满足，您的程序将被评为 Wrong Answer[7]。
• 如果 IOI-kun 报告了输送带的错误方向，您的程序将被评为 Wrong Answer[8]。
• 函数 Answer 必须被恰好调用一次。如果函数 Answer 被调用多次，您的程序将被评为 Wrong Answer[9]。当函数 Solve 结束时，如果函数 Answer 尚未被调用，您的程序将被评为 Wrong Answer[10]。

输入格式

样例评测库将读入以下格式的数据：

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$，如果第 $i$ 条传送带会将产品从 $A_i$ 运输至 $B_i$，那么 $C_i$ 为 $0$，否则 $C_i$ 为 $1$。

输出格式

样例评测库将以下信息输出到 stdout。

-如果你的程序被判断为正确，它报告的函数 Query 调用的数量为 Accepted: 22 。

-如果你的程序被判定为任何类型的错误答案，样例评分员将其类型写为 Wrong Answer[4]。

如果您的程序满足几种类型的错误答案的条件，则样例评测库只报告其中一种。

输入输出样例

样例 #1

3
0 2
2 1
1 0

题目大意

题目描述

在 JOI 有限公司的工厂里，有 $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 会确认每张桌子上是否有产品。如果有产品在桌子上，IOI-kun 会把它们全部拿走。
5. 对于每个在操作 1 中改变了方向的皮带输送机，IOI-kun 都会将其方向恢复到原来的方向。IOI-kun 希望通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

请编写一个程序，根据皮带输送机之间的连接表，实现 IOI-kun 的策略，以通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

实现细节

你需要实现一份 C++ 程序，提交时不需要包含 conveyor.h。

你应该实现以下函数。

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

该函数仅在每个测试用例中被调用一次：

• 参数 $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$，如果 $x_i = 1$，IOI-kun 将反转第 $i$ 个传送带的方向，否则不反转该传送带的方向。
• 参数 $y$ 是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $y_j = 1$，IOI-kun 将在第 $j$ 个桌子上放置一个产品，否则不会在该桌子上放置产品。
• 设 $z$ 是该函数的返回值。它是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $z_j = 1$，则第 $j$ 个桌子上有产品，如果 $z_j = 0$，则第 $j$ 个桌子上没有产品。
• 数组 $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$，如果 $a_i = 0$，则输送带 $i$ 将产品从 $A_i$ 运输到 $B_i$，如果 $a_i = 1$，则将产品从 $B_i$ 运输到 $A_i$。
• 数组 $a$ 的长度必须等于 $N - 1$。如果条件不满足，您的程序将被评为 Wrong Answer[6]。
• 数组 $a$ 中的每个元素都必须为 $0$ 或 $1$。如果条件不满足，您的程序将被评为 Wrong Answer[7]。
• 如果 IOI-kun 报告了输送带的错误方向，您的程序将被评为 Wrong Answer[8]。
• 函数 Answer 必须被恰好调用一次。如果函数 Answer 被调用多次，您的程序将被评为 Wrong Answer[9]。当函数 Solve 结束时，如果函数 Answer 尚未被调用，您的程序将被评为 Wrong Answer[10]。

输入格式

样例评测库将读入以下格式的数据：

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$，如果第 $i$ 条传送带会将产品从 $A_i$ 运输至 $B_i$，那么 $C_i$ 为 $0$，否则 $C_i$ 为 $1$。

输出格式

样例评测库将以下信息输出到 stdout。

-如果你的程序被判断为正确，它报告的函数 Query 调用的数量为 Accepted: 22 。

-如果你的程序被判定为任何类型的错误答案，样例评分员将其类型写为 Wrong Answer[4]。

如果您的程序满足几种类型的错误答案的条件，则样例评测库只报告其中一种。

输入输出样例

样例 #1

3
0 2
2 1
1 0

说明/提示

函数调用		返回值
Solve(3, [0, 2], [2, 1])
	Query([0, 0], [0, 0, 1])	[1, 0, 0]
	Query([1, 0], [1, 0, 1])	[0, 1, 1]
	Query([1, 1], [0, 0, 1])	[0, 0, 1]
	Query([0, 1], [1, 1, 1])	[1, 0, 1]
	Answer([1, 0])

对于对 Query 的第一次调用，另一个可能的返回值是 [0,1,0]。

对于对 Query 的第二次调用，位置为 $0$ 上的产品通过传送带 $0$ 被传送到位置 $2$，并停在那里。请注意，该产品不会被传送带 $1$ 输送到位置 $1$。

注意，这个示例输入不满足任何子任务的限制条件。

下发文件中，sample-02.txt 满足 Subtask $1$ 的限制条件，sample-03.txt 满足 Subtask $2$ 的限制条件。

对于某些测试用例，实际的评测程序是自适应的。这意味着评测程序在开始时没有固定的答案，并根据先前对 Query 函数的调用进行响应。

Translate by

提示

函数调用		返回值
Solve(3, [0, 2], [2, 1])
	Query([0, 0], [0, 0, 1])	[1, 0, 0]
	Query([1, 0], [1, 0, 1])	[0, 1, 1]
	Query([1, 1], [0, 0, 1])	[0, 0, 1]
	Query([0, 1], [1, 1, 1])	[1, 0, 1]
	Answer([1, 0])

对于对 Query 的第一次调用，另一个可能的返回值是 [0,1,0]。

对于对 Query 的第二次调用，位置为 $0$ 上的产品通过传送带 $0$ 被传送到位置 $2$，并停在那里。请注意，该产品不会被传送带 $1$ 输送到位置 $1$。

注意，这个示例输入不满足任何子任务的限制条件。

下发文件中，sample-02.txt 满足 Subtask $1$ 的限制条件，sample-03.txt 满足 Subtask $2$ 的限制条件。

对于某些测试用例，实际的评测程序是自适应的。这意味着评测程序在开始时没有固定的答案，并根据先前对 Query 函数的调用进行响应。

Translate by