题目描述

题目译自 JOISC 2020 Day2 T1「カメレオンの恋 / Chameleon’s Love」

注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++
• C++ 11
• C++ 17
• C++ (NOI)
• C++ 11 (NOI)
• C++ 11 (Clang)
• C++ 17 (Clang)

在 JOI 动物园中，有着 $2N$ 只变色龙，编号为 $1\ldots 2N$。其中，有 $N$ 只变色龙的性别为 X，其余 $N$ 只的性别为 Y。

每只变色龙都有一个原色。关于原色的可公开情报如下：

• 所有性别为 X 的变色龙的原色不同。
• 对于每只性别为 X 的变色龙，都存在唯一的原色与其相同的变色龙，且性别为 Y。

现在，JOI 动物园迎来了恋爱的季节。每只变色龙都爱上了另一只变色龙。关于恋爱对象的可公开情报如下：

• 每只变色龙都很专一于唯一一只异性的变色龙。
• 一只变色龙和它的恋爱对象的原色不同。
• 不存在两只变色龙同时追求另一只变色龙。

你可以召集一部分变色龙来组织一场会议。对于一只参加会议的变色龙 $s$，令 $t$ 为它的恋爱对象。$s$ 的肤色由以下方式决定：

• 如果 $t$ 参加了这场会议，则 $s$ 的肤色为 $t$ 的原色。
• 如果 $t$ 没参加这场会议，则 $s$ 的肤色为 $s$ 的原色。

一只变色龙的肤色可以在不同的会议间发生改变。对于你组织的一场会议，你可以得到场上所有变色龙的肤色的种类数。

由于变色龙也会感到厌烦，所以你最多只能组织 $20\,000$ 场会议。同时你需要根据你得到的信息，确定有哪些变色龙的原色相同。
请你写一个程序在组织不超过 $20\,000$ 场会议的前提下确定所有相同原色的变色龙。

实现细节

你需要提交一个文件。
这个文件的名字应为 $\texttt{chameleon.cpp}$。这个程序应当包含 $\texttt{chameleon.h}$，且其中需要实现以下函数：

• $\texttt{void Solve(int N)}$
  对于每组测试数据，保证这个函数会被恰好调用一次。
  • 其参数 $\texttt N$ 为题目中的 $N$，性别为 X 的变色龙的个数。

你的程序可以调用以下函数：

• \texttt{int Query(const std::vector<int> &p)}
  你可以通过调用这个函数组织一场会议。
  • 参数 $\texttt p$ 是参加这场会议的变色龙的列表。
  • 返回值即为本场会议所有变色龙的肤色的种类数。
  • $\texttt p$ 中的每个元素都应该是一个 $[1,2N]$ 内的整数，否则你的程序将会被判为 Wrong Answer [1]。
  • $\texttt p$ 中的元素不得重复，否则你的程序将会被判为 Wrong Answer [2]。
  • 你的程序不应调用 $\texttt{Query}$ 函数超过 $20\,000$ 次，否则你的程序将会被判为 Wrong Answer [3]。
• $\texttt{void Answer(int a, int b)}$
  你可以通过调用这个函数回答一对原色相同的变色龙。
  • 参数 $\texttt a$ 和 $\texttt b$ 表示变色龙 $a,b$ 的原色相同。
  • 必须保证 $1 \le a,b \le 2N$，否则你的程序将会被判为 Wrong Answer [4]。
  • 你的程序不得以相同的 $a$ 值或 $b$ 值调用此函数两次及以上，否则你的程序将会被判为 Wrong Answer [5]。
  • 如果 $a,b$ 的原色不同，你的程序将会被判为 Wrong Answer [6]。
  • 你的程序应当调用 $\texttt{Answer}$ 函数恰好 $N$ 次，否则你的程序将会被判为 Wrong Answer [7]。

实现提示

• 你的程序可以实现其他函数供内部使用，或使用全局变量。
• 你的程序不得访问标准输入输出流，也不得通过任何方法访问其他文件。不过，你的程序可以输出到标准错误流。

编译与运行

你可以在附加文件中下载到一个压缩文件，其中包含一个样例交互库以测试你的程序。这个压缩文件也包含了一个你应当提交的程序的样例。
样例交互库为 $\texttt{grader.cpp}$。为了测试你的程序，请把 $\texttt{grader.cpp},\texttt{chameleon.h},\texttt{chameleon.cpp}$ 放在同一目录下，并执行以下命令来编译你的程序：

$$\texttt{g++ -std=gnu++14 -O2 -o grader grader.cpp chameleon.cpp}$$

若编译成功，会在当前目录生成一个可执行文件 $\texttt{grader}$。
请注意样例交互库并非实际交互库。样例交互库仅是由一个单一的，从标准输入流读入数据，并将结果输出到标准输出流的过程构成的。

输入格式

样例交互库从标准输入流读入以下数据：

第一行，一个整数 $N$。
第二行，$2N$ 个整数 $Y_i$，表示每只变色龙的性别，若其为 $0$ 则性别为 X，否则为 Y。
第三行，$2N$ 个整数 $C_i$，表示每只变色龙的原色，保证其在 $[1,N]$ 内。
第四行，$2N$ 个整数 $L_i$，表示每只变色龙的恋爱对象。

输出格式

样例交互库向标准输入流输出以下数据：

• 若你的程序是正确的，样例交互库将以 $\texttt{Accepted: 100}$ 的形式输出你调用 $\texttt{Query}$ 的次数。
• 若你的程序被判为 Wrong Answer，样例交互库将以 $\texttt{Wrong Answer [1]}$ 的形式输出其类型。

若你的程序触发了不止一种 Wrong Answer，样例交互库只会输出其中一种。

样例

样例输入 1

4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1

样例调用

调用	子调用	返回值
$\texttt{Solve(4)}$
	$\texttt{Query([])}$	$\texttt0$
	$\texttt{Query([6, 2])}$	$\texttt2$
	$\texttt{Query([8, 1, 6])}$	$\texttt2$
	$\texttt{Query([7, 1, 3, 5, 6, 8])}$	$\texttt4$
	$\texttt{Query([8, 6, 4, 1, 5])}$	$\texttt3$
	$\texttt{Answer(6, 4)}$
	$\texttt{Answer(7, 8)}$
	$\texttt{Answer(2, 1)}$
	$\texttt{Answer(3, 5)}$

在附加文件中，$\texttt{sample-02.txt}$ 满足第一个子任务的限制，$\texttt{sample-03.txt}$ 满足第四个子任务的限制。

数据范围与提示

对于所有数据，满足：

• $2 \le N \le 500$。
• $0 \le Y_i \le 1\ (1 \le i \le 2N)$。
• $1 \le C_i \le N\ (1 \le i \le 2N)$。
• 对于每个 $j\ (1 \le j \le N)$，存在一个唯一的 $i\ (1 \le i \le 2N)$ 满足 $Y_i = 0, C_i = j$。
• 对于每个 $j\ (1 \le j \le N)$，存在一个唯一的 $i\ (1 \le i \le 2N)$ 满足 $Y_i = 1, C_i = j$。
• $1 \le L_i \le 2N\ (1 \le i \le 2N)$。
• $Y_i \ne Y_{L_i}\ (1 \le i \le 2N)$。
• $C_i \ne C_{L_i}\ (1 \le i \le 2N)$。
• $L_k \ne L_l\ (1 \le k < l \le 2N)$。

详细子任务附加条件及分值如下表：

子任务编号	附加限制	分值
$1$	$L_{L_i}=i\ (1 \le i \le 2N)$	$4$
$2$	$N \le 7$	$20$
$3$	$N \le 50$	$20$
$4$	$Y_i = 0\ (1 \le i \le N)$	$20$
$5$	-	$36$