시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB1871198563.910%

문제

You are given two arrays of non-negative integers $a_1, a_2, \dots, a_N$ and $b_1, b_2, \dots, b_N$.

You can perform the following operation several times:

  • Choose a non-negative integer $x$ and an index $1 \leq i < N$. Then change $a_i$ to $a_i \oplus x$ and change $a_{i+1}$ to $a_{i+1} \oplus x$.

Expression $x \oplus y$ means bitwise xor of two numbers $x$ and $y$.
In binary representation, if the $i$-th digit of x and y is equal, then the $i$-th digit of $x \oplus y$ is $0$, and if not, it is $1$.
The given operation exists in all modern programming languages. For example, in C++ and Java, it is represented as $x\ ^{\wedge}\ y$.

You want to convert $\{a_i\}$ to $\{b_i\}$ by performing the minimum number of operations.

Find the minimum number of operations to convert $\{a_i\}$ to $\{b_i\}$.

If you cannot convert $\{a_i\}$ to $\{b_i\}$ with the given operation, print $-1$.

입력

The first line contains an integer $N$, where $N$ denotes the length of the two sequences.

The second line contains $N$ space-separated non-negative integers $a_1, a_2, \dots, a_N$.

The third line contains $N$ space-separated non-negative integers $b_1, b_2, \dots, b_N$.

출력

Print $-1$, if it is impossible to change the sequence $\{a_i\}$ to $\{b_i\}$.

Otherwise, print the minimum number of operations needed to change the sequence $\{a_i\}$ to $\{b_i\}$.

제한

  • $1 \leq N \leq 10^6$
  • $0 \leq a_i, b_i < 2^{30}$ $(1 \le i \le N)$

서브태스크 1 (9점)

This subtask has an additional constraint:

  • $N \le 5$

서브태스크 2 (91점)

This subtask has no additional constraints. 

예제 입력 1

3
1 2 3
3 2 1

예제 출력 1

2

예제 입력 2

3
1 5 3
1 2 3

예제 출력 2

-1

출처

University > KAIST > 2022 KAIST RUN Spring Contest A번

채점 및 기타 정보

  • 예제는 채점하지 않는다.