← 返回题目列表

AtCoder · agc016_d

D. 异或替换

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

分数: 1000 点

问题陈述

有一个长度为 N: a = (a_1, a_2, ..., a_N)。 在这里,每一个 a_i 是一个非负整数。

Snuke可以重复执行以下操作:

  • 让其中的所有元素异或 a be x。选择一个整数 i (1 ≤ i ≤ N)并替换 a_i 与 x.

Snuke 的目标是匹配 a 与另一个序列 b = (b_1, b_2, ..., b_N)。 在这里,每一个 b_i 是一个非负整数。

确定目标是否可以实现,如果答案是肯定的,则找到所需的最少操作次数。

约束

  • 2 ≤ N ≤ 10^5
  • a_i 和 b_i 是整数。
  • 0 ≤ a_i, b_i < 2^{30}

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

输出

如果目标可以实现,则打印所需的最少操作数。 否则,打印 -1 。


示例输入 1

3
0 1 2
3 1 0

示例输出 1

2

首先,对所有元素进行异或 a is 3。 如果我们更换 a_1 与 3, a 变为 分别为 (3, 1, 2).

现在,对所有元素进行异或 a is 0。 如果我们更换 a_3 与 0, a 变为 分别为 (3, 1, 0),匹配 b.


示例输入 2

3
0 1 2
0 1 2

示例输出 2

0

示例输入 3

2
1 1
0 0

示例输出 3

-1

示例输入 4

4
0 1 2 3
1 0 3 2

示例输出 4

5