CF472F Design Tutorial: Change the Goal

There are some tasks which have the following structure: you are given a model, and you can do some operations, you should use these operations to achive the goal. One way to create a new task is to use the same model and same operations, but change the goal. Let's have a try. I have created the following task for Topcoder SRM 557 Div1-Hard: you are given $ n $ integers $ x_{1},x_{2},...,x_{n} $ . You are allowed to perform the assignments (as many as you want) of the following form $ x_{i} $ ^= $ x_{j} $ (in the original task $ i $ and $ j $ must be different, but in this task we allow $ i $ to equal $ j $ ). The goal is to maximize the sum of all $ x_{i} $ . Now we just change the goal. You are also given $ n $ integers $ y_{1},y_{2},...,y_{n} $ . You should make $ x_{1},x_{2},...,x_{n} $ exactly equal to $ y_{1},y_{2},...,y_{n} $ . In other words, for each $ i $ number $ x_{i} $ should be equal to $ y_{i} $ .

The first line contains an integer $n\ (1 ≤ n ≤ 10000)$. The second line contains $n$ integers: $x_1$ to $x_n\ (0 ≤ x_i ≤ 10^9)$. The third line contains $n$ integers: $y_1$ to $y_n (0 ≤ y_i ≤ 10^9)$.

If there is no solution, output `-1`. If there is a solution, then in the first line output an integer $m\ (0 ≤ m ≤ 1000000)$ – the number of assignments you need to perform. Then print $m$ lines, each line should contain two integers $i$ and $j (1 ≤ i, j ≤ n)$, which denote assignment $x_i$ ^= $x_j$. If there are multiple solutions you can print any of them. We can prove that under these constraints if there exists a solution then there always exists a solution with no more than $10^6$ operations.

Assignment $ a $ ^= $ b $ denotes assignment $ a $ = $a$ ^ $ b $ , where operation "^" is bitwise XOR of two integers.