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.

存在一些具有如下结构的任务：你被给定一个模型，你可以执行某些操作，你需要利用这些操作来达成目标。构造新任务的一种方法是使用相同的模型和相同的操作，但改变目标。

我们来尝试一下。我为 Topcoder SRM 557 Div1-Hard 构造了如下任务：给你 $n$ 个整数 $x_1,\,x_2,\,\dots,\,x_n$。你被允许执行任意多次如下形式的赋值操作：x_i \mathrel{\text{^=}} x_j（在原任务中要求 $i$ 和 $j$ 必须不同，但本任务中允许 $i = j$）。目标是最大化所有 $x_i$ 的和。

现在我们仅改变目标。你还会被给定 $n$ 个整数 $y_1,\,y_2,\,\dots,\,y_n$。你需要将 $x_1,\,x_2,\,\dots,\,x_n$ 恰好变为 $y_1,\,y_2,\,\dots,\,y_n$。换句话说，对每个 $i$，需满足 $x_i = 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 ≤ 109). The third line contains n integers: _y_1 to y__n (0 ≤ y__i ≤ 109).

第一行包含一个整数 $n$（$1 \leq n \leq 10000$）。第二行包含 $n$ 个整数：$x_1$ 到 $x_n$（$0 \leq x_i \leq 10^9$）。第三行包含 $n$ 个整数：$y_1$ 到 $y_n$（$0 \leq y_i \leq 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 106 operations.

如果无解，输出 -1。

如果有解，则在第一行输出一个整数 $m$（$0 \le m \le 1000000$），表示你需要执行的赋值操作次数。随后输出 $m$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i, j \le n$），表示执行赋值操作 x_i \mathrel{\text{^=}} x_j。

若存在多个解，可输出任意一个。我们可证明：在本题约束下，若解存在，则必存在一个操作次数不超过 $10^6$ 的解。

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

赋值操作 a ^= b 表示 a = a ^ b，其中运算符 ^ 表示两个整数的按位异或（XOR）运算。