Arranging Toy Displays

Aligning toys

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

Xing Yang has N toys, each of which with a type Ti

He also has N displays, each of which can only hold a toy type Di

In 1 operation, he can replace the type of toy i Ti with the value K, where K is the XOR of the types of all toys.

Determine if XY can make the types of all toys such that Ti = Di for all toys, and find how many operations he will require.

Constraints

  • 2 ≤ N ≤ 105
  • Ti and Di are integers.
  • 0 ≤ Ti, Di < 230

Input

Input is given from Standard Input in the following format:

N
T1 T2 ... TN
D1 D2 ... DN

Output

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

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 T1 with 3, T becomes (3, 1, 2).

Now, the XOR of all the elements of a is 0. If we replace T3 with 0, T 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

Submitting to 'Arranging Toy Displays'


You're not logged in! Click here to login


Submitting to 'Arranging Toy Displays'


You're not logged in! Click here to login


Submitting .cpp to 'Arranging Toy Displays'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 256MB
No. of ACs: 18
Your best score: 0
Source: AGC 016D

Subtask Score
1 0
2 100