[AGC016D] XOR Replace

题意翻译

题意:一个序列,一次操作可以将某个位置变成整个序列的异或和。 问最少几步到达目标序列。

题目描述

[problemUrl]: https://agc016.contest.atcoder.jp/tasks/agc016_d 長さ $ N $ の数列 $ a\ =\ (a_1,\ a_2,\ ...,\ a_N) $ があります。 ただし、各 $ a_i $ は $ 0 $ 以上の整数です。 すぬけ君は次の操作を繰り返し行うことができます。 - $ a $ のすべての要素の XOR を $ x $ とする。 整数 $ i $ ( $ 1\ \leq\ i\ \leq\ N $ ) をひとつ選び、 $ a_i $ を $ x $ に置き換える。 すぬけ君の目標は、 $ a $ を数列 $ b\ =\ (b_1,\ b_2,\ ...,\ b_N) $ に一致させることです。 ただし、各 $ b_i $ は $ 0 $ 以上の整数です。 目標が達成可能か判定し、達成可能ならば必要な操作回数の最小値を求めてください。

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ b_1 $ $ b_2 $ $ ... $ $ b_N $ ```

输出格式


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

输入输出样例

输入样例 #1

3
0 1 2
3 1 0

输出样例 #1

2

输入样例 #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

输入样例 #5

3
0 1 2
3 1 0

输出样例 #5

2

输入样例 #6

2
1 1
0 0

输出样例 #6

-1

输入样例 #7

4
0 1 2 3
1 0 3 2

输出样例 #7

5

说明

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ a_i $ , $ b_i $ は整数である。 - $ 0\ \leq\ a_i,\ b_i\ <\ 2^{30} $ ### 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\ \leq\ i\ \leq\ 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\ \leq\ N\ \leq\ 10^5 $ - $ a_i $ and $ b_i $ are integers. - $ 0\ \leq\ a_i,\ b_i\ <\ 2^{30} $ ### Sample Explanation 1 最初、 $ a $ のすべての要素の XOR は $ 3 $ です。 $ a_1 $ を選んで $ 3 $ に置き換えると、 $ a\ =\ (3,\ 1,\ 2) $ となります。 次に、 $ a $ のすべての要素の XOR は $ 0 $ です。 $ a_3 $ を選んで $ 0 $ に置き換えると、 $ a\ =\ (3,\ 1,\ 0) $ となり、 $ b $ に一致します。 ### Sample Explanation 5 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 $ .