Description

In the JOI Zoo, there are $2\times N$ chameleons. $N$ of them have gender $\rm X$, and the other $N$ have gender $\rm Y$.

Each chameleon has its original color, with the following constraints:

• The colors of the $\rm X$-gender chameleons are pairwise distinct.
• For each $\rm X$-gender chameleon, there exists a $\rm Y$-gender chameleon with the same color.

Now each chameleon loves exactly one other chameleon, under the following rules:

• Each chameleon only loves a chameleon of the opposite gender.
• Each chameleon and the chameleon it loves have different original colors.
• There is no chameleon that is loved by two different chameleons.

Now you may organize meetings of some chameleons. For each chameleon $s$ in the meeting, let $t$ be the chameleon that $s$ loves.

• If $t$ attends the meeting, then the skin color of $s$ becomes the original color of $t$.
• Otherwise, the skin color of $s$ remains the original color of $s$.

For each meeting you organize, you can count the number of distinct skin colors.

By holding at most $2\times 10^4$ meetings, you must determine every pair of chameleons that share the same original color.

Interaction Details

You need to declare two functions before your program:

• int Query(const std::vector<int> &p).
• void Answer(int a, int b).

You need to implement one function: void Solve(int N).

• It is called exactly once for each test case.
• The meaning of $N$ is as described in the statement.

Your program may call the following functions:

• int Query(const std::vector<int> &p)

  • You may call this function to organize a chameleon meeting.
    • $p$ is the list of chameleons attending the meeting.
    • It returns the number of distinct colors among the attending chameleons.
    • All numbers in $p$ must be between $1$ and $2\times N$, otherwise it will return Wrong Answer [1].
    • All numbers in $p$ must be pairwise distinct, otherwise it will return Wrong Answer [2].
    • You may call this function at most $2\times 10^4$ times; if you exceed this limit, it will return Wrong Answer [3].

• void Answer(int a, int b)

  • Call this function to submit a pair of chameleons with the same original color.
    • Parameters $a$ and $b$ indicate that chameleon $a$ and chameleon $b$ have the same original color.
    • You must ensure $1\le a,b\le 2\times N$, otherwise it will return Wrong Answer [4].
    • You must ensure that every chameleon you submit is different from all previously submitted chameleons, otherwise it will return Wrong Answer [5].
    • If the original colors of $a$ and $b$ are different, it will return Wrong Answer [6].
    • You must call this function exactly $N$ times, otherwise it will return Wrong Answer [7].

If you never violate any of the restrictions during the interaction, then you will be accepted.

Input Format

The input format of the interactive library is as follows:

The first line contains an integer $N$.

The second line contains $2\times N$ integers $Y_i$, indicating the gender of each chameleon. If $Y_i=0$, the gender is $\rm X$; if $Y_i=1$, the gender is $\rm Y$.

The third line contains $2\times N$ integers $C_i$, where $C_i$ is the color of chameleon $i$.

The fourth line contains $2\times N$ integers $L_i$, where $L_i$ indicates that chameleon $i$ likes (loves) chameleon $L_i$. ("稀饭" is a colloquial form of "喜欢", meaning "like".)

Output Format

The output format of the interactive library is as follows:

If you get AC, it outputs one line Accepted: x, where $x$ is the number of times you called int Query(const std::vector<int> &p).

If you get WA, it outputs one line Wrong Answer [type], where $type$ is the reason for WA. See the interaction details.

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

Hint

Sample Explanation

The sample calls are as follows: | Library Call | Your Call | Return Value | | :-: | :-: | :-: | | Solve(4) | | | | | Query([]) | $0$ | | | Query([6, 2]) | $2$ | | | Query([8, 1, 6]) | $2$ | | | Query([7, 1, 3, 5, 6, 8]) | $4$ | | | Query([8, 6, 4, 1, 5]) | $3$ | | | Answer(6, 4) | | | | Answer(7, 8) | | | | Answer(2, 1) | | | | Answer(3, 5) | |

sample-02.txt satisfies the constraints of Subtask 1, and sample-03.txt satisfies the constraints of Subtask 4.

Subtasks and Constraints

For $100\%$ of the data, it is guaranteed that $2\le N\le 500$, $0\le Y_i\le 1$, $1\le C_i\le N$, $1\le L_i\le 2\times N$, $Y_i\not=Y_{L_i}$, $C_i\not=C_{L_i}$, and all $L_i$ are pairwise distinct.

Notes

This problem is translated from The 19th Japanese Olympiad in Informatics Spring Training Camp Day 2 T1 カメレオンの恋.

Translated by ChatGPT 5