Informatica Online Judge

  이상한 기계 [2403 / 0963]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 7   Total Tried : 52


The Champion of this Problem (C++) : gs18103 - ms / 1176byte
My Best Submission (C++) : N/A

[36th 최은수(gs18115)]
Writer ID : [gs18115]

Background

8월 14일은 준호의 생일이다!
준호의 생일이 2주가 지났지만, 준호에게 아직 생일 선물을 주지 못한 은수는 준호에게 수열을 하나 선물하기로 했다.
은수는 현재 정수 수열 s를 가지고 있으며, 수열 s의 길이는 N이다.
은수는 준호에게 길이 N의 정수 수열 t를 선물하기로 하였고, 수열 t를 만들기 위해 가지고 있는 이상한 기계를 이용해서 수열 s를 변형하기로 하였다.

은수가 가진 기계는 다음과 같은 연산을 수행한다:
수열에서 한 원소를 뽑아서, 그 원소를 지우고 지운 자리에 지운 원소를 포함한 모든 원소를 xor한 값을 넣는다.

은수의 기계는 고장이 나기 쉽기 때문에, 최대 10^18번만 사용할 수 있다.
또한, 만약을 대비해서 은수는 최대한 기계를 적게 사용하고 싶다.

은수가 준호에게 수열 t를 선물할 수 있을지 구해 주자!
만약 수열을 선물할 수 있다면, 기계의 최소 사용 횟수도 구해 주자!

Input

두 수열 s, t의 길이 N이 주어진다. (2 <= N <= 100,000)
두 번째 줄에는 N개의 수가 주어지고, i번째 수는 수열 s의 i번째 수 s_i(0 <= s_i < 2^30)를 의미한다.
세 번째 줄에는 N개의 수가 주어지고, i번째 수는 수열 t의 i번째 수 t_i(0 <= t_i < 2^30)를 의미한다.

Output

수열 s를 t로 바꾸기 위해 필요한 기계의 최소 사용 횟수를 출력한다.
만약 기계를 10^18번 이하로 사용하여 s를 t로 바꿀 수 없다면, -1을 출력한다.

IO Example

입력1
2
1 0
2 2

출력1
-1

입력2
4
1 2 3 4
2 3 4 4

출력2
3


* 예제는 입출력에 포함되지 않는다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]