수열 변환

면접 대비

시간 제한3초메모리 제한1024 MB

요약

두 배열 a와 b가 주어질 때, 인접한 두 원소에 같은 값 x를 xor하는 연산으로 a를 b로 바꾸는 최소 횟수를 구합니다. 불가능하면 -1을 출력합니다.

난이도: 보통10점 중 4점
유형: 누적 합, 비트 연산
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 인 음이 아닌 정수 배열 $a_1, a_2, \dots, a_N$ 과 $b_1, b_2, \dots, b_N$ 이 주어진다.

다음 연산을 여러 번 수행할 수 있다. 음이 아닌 정수 $x$ 와 인덱스 $1 \leq i < N$ 을 고른다. 그러면 $a_i$ 는 $a_i \oplus x$ 가 되고, $a_{i+1}$ 은 $a_{i+1} \oplus x$ 가 된다. 여기서 $\oplus$ 는 비트 단위 배타적 논리합(xor)이다.

$a$ 를 $b$ 로 바꾸는 데 필요한 최소 연산 횟수를 구하라. 바꿀 수 없으면 -1을 출력한다.

입력

첫 번째 줄에 두 수열의 길이 $N$ 이 주어진다.

두 번째 줄에 공백으로 구분된 음이 아닌 정수 $a_1, a_2, \dots, a_N$ 이 주어진다.

세 번째 줄에 공백으로 구분된 음이 아닌 정수 $b_1, b_2, \dots, b_N$ 이 주어진다.

출력

$a$ 를 $b$ 로 바꿀 수 없으면 -1을 출력한다. 그렇지 않으면 필요한 최소 연산 횟수를 출력한다.

제한

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

예제2

예제 1
입력
```
3
1 2 3
3 2 1
```
예상 출력
```
2
```
예제 2
입력
```
3
1 5 3
1 2 3
```
예상 출력
```
-1
```