← 返回题目列表

Codeforces · 472/F

F. 设计教程:改变目标

中文机器翻译题面 查看原题

有一些任务具有以下结构:给你一个模型,你可以做一些操作,你应该使用这些操作来实现目标。创建新任务的一种方法是使用相同的模型和相同的操作,但改变目标。

我们来尝试一下。我为 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,其中运算“^”是两个整数的按位异或。