/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
長さ N の数列 a = (a_1, a_2, ..., a_N) があります。 ただし、各 a_i は 0 以上の整数です。
すぬけ君は次の操作を繰り返し行うことができます。
- a のすべての要素の XOR を x とする。 整数 i (1 ≤ i ≤ N) をひとつ選び、a_i を x に置き換える。
すぬけ君の目標は、a を数列 b = (b_1, b_2, ..., b_N) に一致させることです。 ただし、各 b_i は 0 以上の整数です。
目標が達成可能か判定し、達成可能ならば必要な操作回数の最小値を求めてください。
制約
- 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