Problem C
Dandelion Chaos

Before Gösta died of old age, scientists discovered how to make people immortal. How this was achieved is left as an exercise for the reader. Gösta has a meadow of dandelions. After a long wait, it is finally fully grown, and he can now create dandelion soda with the dandelions (see Dandelions). Interestingly, not all dandelions are exactly the same: he has discovered that there are $N$ different species of dandelions in his meadow. Naturally, he now wants to know if certain dandelion species create tastier soda than others. After some effort, Gösta has managed to pick exactly $2$ specimens of each species. Just as he was about to begin analyzing them, he accidentally stumbles and mixes all the dandelions together. Disaster!

Since the dandelions are very visually similar, he will need to use his pollen analysis machine. It works by allowing all the dandelions in it to bloom, and then it can analyze the pollen. It can then determine the number of unique species of dandelions present. Unfortunately, it cannot dintinguish whether there is one or two of a particular species, as the amount of pollen can vary greatly from one dandelion to another. He has numbered all his dandelions from $1$ to $2N$.

There are two ways in which you can use the machine:

• Insert a dandelion into the machine.

• Remove a dandelion from the machine (that is already inside of it).

After you insert or remove a dandelion from the machine, you immediately find out the number of unique species of dandelions present in it. Gösta now wants your help to use the machine to find which pairs of dandelions are of the same species. Since he is immortal, he is not in a hurry, but still wants to finish within a "reasonable" time. Therefore, he can accept that you use the machine at most one million ($10^6$) times.

Implementation

Your solution to the problem must be written in C++. It should include the file maskroskaos.h. You shall not create a main function. Instead, you shall implement the function

• void Solve(int $N$)
  This function is called once for each testcase, and serves as the main function of your program.

  • The parameter $N$ ($1 \leq N \leq 43000$) is the number of kinds of species that Gösta has collected.

  Your program can use the following functions to solve the problem.

  • int Query(int $x$)
    Where $x$ ($1 \leq X \leq 2N$) is the index of one the $2N$ dandelions. If $x$ is not present in the machine, it is inserted. If $x$ is already present in the machine, it is removed. The return value is the number of unique species of dandelions present in the machine after $x$ has been inserted or removed. If you call this function more than $10^6$ or call it with an $x$ that does not satisfy $1 \leq x \leq 2N$, you get Wrong Answer.

  • int Answer(int a, int b)
    When you call this function, you claim that the dandelions with index $a$ and $b$ are of the same species. If you do any of the following, you will get Wrong Answer.

    • If Answer is called with the same dandelion more than once. For example, the call Answer(1,2) followed by Answer(1,3) will give you Wrong Answer because $1$ is present in both.

    • $1 \leq a,b \leq 2N$ is not satisfied.

    • The dandelions with index $a$ and $b$ are not of the same species.

    • You return from solve without having called Answer exactly $N$ times.

Note: the functions Query and Answer should be called from the function Solve. (Se example code in maskroskaos.cpp)

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Testing your solution

To facilitate testing of your program, we provide a sample program and a sample judge. These can be downloaded from the attachments at the bottom of the page.

To test the program, you can execute the following command:

• g++ -o grader grader.cpp maskroskaos.cpp

This will create the file "grader", which you can then run to test the program. Note that this sample judge differs from the judge used for the task. However, it is guaranteed that the real judge is not adaptive. This means that the answer is determined before your program is run, and it cannot change it during runtime. Your program must not read from or write to standard input/output (i.e. reading or writing to the terminal). Doing so will likely cause confusing errors.

Input format of sample judge

The sample judge will read input in the following format:

• One line with with the integer $N$.

• $N$ lines that each contain the integers $a$ and $b$ ($1 \leq a,b \leq 2N$). This means that the dandelions with index $a$ and $b$ are of the same species.

Output format of sample judge

If your program solved the test case, the judge will write "Accepted. Queries: $q$", where $q$ is the number of times your program called Query.

If your program incorrect, it will write "WA. $e$", where $e$ is the mistake your program made. If your program has multiple errors, it will only write the first error it made.

Example interaction

Consider the following input to the judge:

3
1 5
2 4
3 6

A valid interaction that solves the problem can be as follows: