P10258 [COCI 2023/2024 #5] Bitovi

**Translated from [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T2 “[Bitovi](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)”.**

Which came first, the chicken or the egg? Is it better to live as a millionaire for one hundred years, or spend seven days in poverty? How do you become a chess master? How do you pull up blinds? How do you pass final exams? How do you train a dragon? These are all interesting questions we can think about after the contest, but now we will ask a less interesting computer science question. You are given two sets of numbers $A$ and $B$, both of size $N$. In one operation, you may choose any element from set $A$ and change any one bit in its binary representation. The resulting number must not be an element of set $A$ before the change. For example, the binary representation of $5$ is $0101_2$. With one operation, it can become $13=1101_2$, $1=0001_2$, $7=0111_2$, or $4=0100_2$. Find a sequence of operations that transforms set $A$ into set $B$. Two sets are considered equal if they have the same size and there is no element in $A$ that does not belong to $B$. Note: The number of operations does not have to be minimal, but it must satisfy the limits of the task.

The first line contains an integer $N$ ($1 \le N \le 2^{15}$), the size of sets $A$ and $B$. The second line contains $N$ distinct integers $a_i$ ($0 \le a_i < 2^{15}$), the elements of set $A$. The third line contains $N$ distinct integers $b_i$ ($0 \le b_i < 2^{15}$), the elements of set $B$.

On the first line, output the number of operations, not exceeding $2^{19}$. Then output several lines. Each line should contain $x, y$ ($0 \le x, y < 2^{15}$), meaning that you change $x$ in set $A$ into $y$. The binary representations of $x$ and $y$ must differ in exactly one bit. Also, it must hold that $x \in A$ and $y \not\in A$.

### Sample Explanation 1 If we first perform $0\ 1$ and then $1\ 3$, then between the two operations, set $A$ will contain two equal elements, which is not allowed. Another possible solution is $2\ 3$, $0\ 2$. ### Sample Explanation 2 $31=11111_2$. If we modify bits from the least significant bit to the most significant bit, we can obtain $30, 28, 24, 16$, and $0$ in order. After all operations, $A$ and $B$ are the same. ### Subtasks | Subtask | Points | Constraints | | :--: | :--: | :--: | | 1 | 10 | $a_i,b_i \le 2^{14}$ | | 2 | 15 | $N \le 7$ | | 3 | 30 | $N \le 2^7$ | | 4 | 15 | No additional constraints. | Translated by ChatGPT 5