Home

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}$

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