AtCoder Grand Contest 016

D - XOR Replace


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 1000

問題文

長さ N の数列 a = (a_1, a_2, ..., a_N) があります。 ただし、各 a_i0 以上の整数です。

すぬけ君は次の操作を繰り返し行うことができます。

  • a のすべての要素の XOR を x とする。 整数 i (1 ≤ i ≤ N) をひとつ選び、a_ix に置き換える。

すぬけ君の目標は、a を数列 b = (b_1, b_2, ..., b_N) に一致させることです。 ただし、各 b_i0 以上の整数です。

目標が達成可能か判定し、達成可能ならば必要な操作回数の最小値を求めてください。

制約

  • 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 のすべての要素の XOR は 3 です。 a_1 を選んで 3 に置き換えると、a = (3, 1, 2) となります。

次に、a のすべての要素の XOR は 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

Score : 1000 points

Problem Statement

There is a sequence of length N: a = (a_1, a_2, ..., a_N). Here, each a_i is a non-negative integer.

Snuke can repeatedly perform the following operation:

  • Let the XOR of all the elements in a be x. Select an integer i (1 ≤ i ≤ N) and replace a_i with x.

Snuke's objective is to match a with another sequence b = (b_1, b_2, ..., b_N). Here, each b_i is a non-negative integer.

Determine whether the objective is achievable, and find the minimum necessary number of operations if the answer is positive.

Constraints

  • 2 ≤ N ≤ 10^5
  • a_i and b_i are integers.
  • 0 ≤ a_i, b_i < 2^{30}

Input

Input is given from Standard Input in the following format:

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

Output

If the objective is achievable, print the minimum necessary number of operations. Otherwise, print -1 instead.


Sample Input 1

3
0 1 2
3 1 0

Sample Output 1

2

At first, the XOR of all the elements of a is 3. If we replace a_1 with 3, a becomes (3, 1, 2).

Now, the XOR of all the elements of a is 0. If we replace a_3 with 0, a becomes (3, 1, 0), which matches b.


Sample Input 2

3
0 1 2
0 1 2

Sample Output 2

0

Sample Input 3

2
1 1
0 0

Sample Output 3

-1

Sample Input 4

4
0 1 2 3
1 0 3 2

Sample Output 4

5

Submit提出する