有一些任务具有以下结构:给你一个模型,你可以做一些操作,你应该使用这些操作来实现目标。创建新任务的一种方法是使用相同的模型和相同的操作,但改变目标。
我们来尝试一下。我为 Topcoder SRM 557 Div1-Hard 创建了以下任务:给您 n 个整数 x1、x2、...、xn。您可以执行以下形式的作业(任意数量) xi ^= xj (在原始任务中 i 和 j 必须不同,但在本任务中我们允许 i 等于 j)。目标是最大化所有 xi 的总和。
现在我们只是改变目标。还给你 n 个整数 y1, y2, ..., yn。您应该使 x1, x2, ..., xn 完全等于 y1, y2, ..., yn。换句话说,对于每个 i 数,xi 应等于 yi。
输入
第一行包含一个整数 n (1 ≤ n ≤ 10000)。第二行包含 n 个整数:x1 到 xn (0 ≤ xi ≤ 109)。第三行包含 n 个整数:y1 到 yn (0 ≤ yi ≤ 109)。
输出
如果无解,则输出-1。
如果有解,则在第一行输出一个整数 m (0 ≤ m ≤ 1000000) – 您需要执行的作业数量。然后打印 m 行,每行应包含两个整数 i 和 j (1 ≤ i, j ≤ n),表示赋值 xi ^= xj。
如果有多个解决方案,您可以打印其中任何一个。我们可以证明,在这些约束下,如果存在解,则总存在一个操作数不超过 106 的解。
示例
输入 #1
2 3 5 6 0
输出 #1
2 1 2 2 2
输入 #2
5 0 0 0 0 0 1 2 3 4 5
输出 #2
-1
输入 #3
3 4 5 6 1 2 3
输出 #3
5 3 1 1 2 2 2 2 3 3 1
输入#4
3 1 2 3 4 5 6
输出#4
-1
注意
赋值 a ^= b 表示赋值 a = a ^ b,其中运算“^”是两个整数的按位异或。