Problem:


Score : 1000 points

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}

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

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



Sample input:
3
0 1 2
3 1 0


Sample output:
2

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}

    N = I()
    A = LI()
    B = LI()
    uf = UnionFind(N+1)
    Da = defaultdict(list)
    Db = defaultdict(list)
    bita = 0

    same = [False]*(N+1)
    for i in range(N):
        if A[i]==B[i]:
            same[i] = True
    if sum(same)==N:
        print(0)
        return

    for i,a in enumerate(A):
        bita ^= a
        if same[i]:
            continue
        Da[a].append(i)
    Da[bita].append(N)
    bitb = 0
    for i,b in enumerate(B):
        bitb ^= b
        if same[i]:
            continue
        Db[b].append(i)
    Db[bitb].append(N)
    #print(Da)
    #print(Db)
    for key,a in Da.items():
        if len(Db[key])!=len(a):
            print(-1)
            return

    for key,a in Da.items():
        uf.unite(a[0],Db[key][0])
        if len(a)==1:
            continue
        for i in a[1:]:
            uf.unite(a[0],i)
    for b in Db.values():
        if len(b)==1:
            continue
        for i in b[1:]:
            uf.unite(b[0],i)

    if uf.size(N)==N-sum(same):
        ans = uf.size(N)
        if bita!=bitb:
            ans -= 1
        print(ans)
        return

    ans = 0
    used = [False]*(N+1)
    for i in range(N):
        #print(ans)
        if same[i]:
            continue
        p = uf.find(i)
        if used[p]:
            continue
        used[p] = True
        ans += (-uf.parent[p]+1)
        #print(ans)
    #if sum(used)>1:
    #    ans += 1
    if uf.size(N)>1:
        ans -= 1
    if bita!=bitb or len(Da[bita])>1:
        ans -= 1
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
5
0 2 3 6 9
2 9 0 6 3

5
0 2 3 6 9
2 9 0 6 14
# 4
5
0 2 3 6 9
2 3 0 6 14
# 5
5
0 2 3 6 9
2 0 3 9 14
# 5
4
1 2 4 8
2 1 8 4
# 6
"""

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from functools import reduce
import operator
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

N = int(readline())
A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

a_xor = reduce(operator.xor,A)
b_xor = reduce(operator.xor,B)

if any(x != y for x,y in zip(sorted(A + [a_xor]),sorted(B + [b_xor]))):
    print(-1)
    exit()

Adiff = [x for x,y in zip(A,B) if x != y]
Bdiff = [y for x,y in zip(A,B) if x != y]
x_to_i = {x:i for i,x in enumerate(set(Adiff + [a_xor]))}
row = [x_to_i[x] for x in Adiff]
col = [x_to_i[x] for x in Bdiff]
if a_xor != b_xor:
    row.append(x_to_i[a_xor])
    col.append(x_to_i[b_xor])
V = len(x_to_i)
graph = csr_matrix(([1]*len(row),(row,col)),(V,V))
Ncomp,comp = connected_components(graph)

counter = [0] * Ncomp
for x in Adiff:
    counter[comp[x_to_i[x]]] += 1
c = comp[x_to_i[a_xor]]
counter[c] += 1

answer = sum(x+1 for x in counter) - 2
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import reduce
from operator import xor


def dfs(s, links, fixed):
    q = [s]
    while q:
        v = q.pop()
        if fixed[v]:
            continue
        fixed[v] = True
        q.extend(links[v])


def solve(n, aaa, bbb):
    a0 = reduce(xor, aaa, 0)
    b0 = reduce(xor, bbb, 0)
    aaa.append(a0)
    bbb.append(b0)
    ad = defaultdict(set)
    bd = defaultdict(set)
    for i, a in enumerate(aaa):
        ad[a].add(i)
    for i, b in enumerate(bbb):
        bd[b].add(i)
    ac = {a: len(s) for a, s in ad.items()}
    bc = {b: len(s) for b, s in bd.items()}
    if ac != bc:
        return -1
    links = defaultdict(set)
    ans = 0
    for a, b in zip(aaa, bbb):
        if a == b:
            continue
        ans += 1
        links[a].add(b)

    if not ans:
        return 0

    if a0 == b0:
        links[a0].add(b0)
    else:
        ans -= 1

    fixed = {a: False for a in links}
    for a in links:
        if fixed[a]:
            continue
        ans += 1
        dfs(a, links, fixed)

    return ans - 1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(solve(n, aaa, bbb))

Submission status: Accepted

Solution code:
n,a,b=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0]
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
na,nb=sorted(a),sorted(b)
if na!=nb:
	print("-1")
	exit()
f=dict()
def find(x):
	if f[x]==x:
		return x
	else:
		f[x]=find(f[x])
		return f[x]
ans=0
for i in range(n):
	if a[i]!=b[i]:
		f[a[i]]=a[i]
f[a[n]]=a[n]
for i in range(n):
	if a[i]!=b[i]:
		ans+=1
		f[find(b[i])]=find(a[i])
for i in f:
	if i==f[i]:
		ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
s=0
for i in A:
  s=s^i
if sorted(A)==sorted(B):
  ans=0
  for i in range(N+10):
    if A[i]!=B[i]:
      ans+=1
  print(ans+1)
  exit()
else:#OK
  ans=0
  A+=[s]
  L=sorted(A)
  R=sorted(B)
  for i in range(N):
    if L[i]!=R[i]:
      L.remove(L[i])
      break
    if i==N-1:
      L.remove(L[N])
  if sorted(L)!=sorted(R):
    print(-1)
    exit()
  for i in range(N):
    if A[i]!=B[i]:
      ans+=1
  print(ans)

Submission status: Runtime Error

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}

    N = I()
    A = LI()
    B = LI()
    uf = UnionFind(N+1)
    Da = defaultdict(list)
    Db = defaultdict(list)
    bita = 0

    same = [False]*(N+1)
    for i in range(N):
        if A[i]==B[i]:
            same[i] = True
    if sum(same)==N:
        print(0)
        return

    for i,a in enumerate(A):
        bita ^= a
        if same[i]:
            continue
        Da[a].append(i)
    Da[bita].append(N)
    bitb = 0
    for i,b in enumerate(B):
        bitb ^= b
        if same[i]:
            continue
        Db[b].append(i)
    Db[bitb].append(N)
    if bita==bitb:
        same[N] = True
    #print(Da)
    #print(Db)
    for key,a in Da.items():
        if len(Db[key])!=len(a):
            print(-1)
            return

    for key,a in Da.items():
        uf.unite(a[0],Db[key][0])
        if len(a)==1:
            continue
        for i in a[1:]:
            uf.unite(a[0],i)
    for b in Db.values():
        if len(b)==1:
            continue
        for i in b[1:]:
            uf.unite(b[0],i)

    if uf.size(N)==N+1-sum(same):
        ans = uf.size(N)
        if bita!=bitb:
            ans -= 1
        print(an)
        return

    ans = -1
    used = [False]*(N+1)
    for i in range(N+1):
        #print(ans)
        if same[i]:
            continue
        p = uf.find(i)
        if used[p]:
            continue
        used[p] = True
        ans += (-uf.parent[p]+1)
        #print(ans)
    #if sum(used)>1:
    #    ans += 1
    if uf.size(N)>1:
        ans -= 1
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
5
0 2 3 6 9
2 9 0 6 3

5
0 2 3 6 9
2 9 0 6 14
# 4
5
0 2 3 6 9
2 3 0 6 14
# 5
5
0 2 3 6 9
2 0 3 9 14
# 5
"""

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

x = a[0]
for i in range(1,n):
    x = x^a[i]


a.append(x)

a_=[]
b_=[]
for i in range(n):
    if a[i]!=b[i]:
        a_.append(a[i])
        b_.append(b[i])

a_.sort()
b_.sort()
flag=True

boo = False
for i in range(len(a_)):
    if a_[i]!=b_[i]:
        if boo == False:
            boo =True
        else:
            print('-1')
            flag=False
            
if flag==True:
    if boo = True:
        print(len(b_))
    else:
        print(len(b_)+1)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

x = a[0]
for i in range(1,n):
    x = x^a[i]


a.append(x)

a_=[]
b_=[]
for i in range(n):
    if a[i]!=b[i]:
        a_.append(a[i])
        b_.append(b[i])

a_.sort()
b_.sort()

boo = False
for i in range(len(a_)):
    if a_[i]!=b_[i]:
        if boo == False:
            boo =True
        else:
            print('-1')
            return
print(len(b_))

Submission status: Runtime Error

Solution code:
n,a,b=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0]
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
na,nb=sorted(a),sorted(b)
if na!=nb:
	print("-1")
	exit()
f=dict()
def find(x):
	if f[x]==x:
		return x
	else:
		f[x]=find(f[x])
		return f[x]
ans=0
for i in range(n):
	if a[i]!=b[i]:
		f[a[i]]=a[i]
f[a[n]]=a[n]
for i in range(n):
	if a[i]!=b[i]:
		ans+=1
		f[find(b[i])]=find(a[i])
for i,j in f:
	if i==j:
		ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
n,a,b=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0]
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
na,nb=sorted(a),sorted(b)
if sum([na[i]!=nb[i] for i in range(n+1)]):
	print("-1")
	exit()
f=dict()
def find(x):
	if f[x]==x:
		return x
	else:
		f[x]=find(f[x])
		return f[x]
ans=0
for i in range(n):
	if a[i]!=b[i]:
		f[a[i]]=a[i]
f[a[n]]=a[n]
for i in range(n):
	if a[i]!=b[i]:
		ans+=1
		f[find(b[i])]=find(a[i])
for i,j in f:
	if i==j:
		ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
n,a,b,ax,bx=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0],0,0
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
na,nb=a,b
a,b=sorted(a),sorted(b)
if sum([a[i]!=b[i] for i in range(n+1)]):
	print("-1")
	exit()
f=dict()
def find(x):
	if f[x]==x:
		return x
	else:
		f[x]=find(f[x])
		return f[x]
ans=0
for i in range(n):
	if na[i]!=nb[i]:
		f[na[i]]=na[i]
f[na[n]]=na[n]
for i in range(n):
	if na[i]!=nb[i]:
		ans+=1
		f[find(nb[i])]=find(na[i])
for i,j in f:
	if i==j:
		ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
n,a,b,ax,bx=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0],0,0
na,nb=a,b
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
a,b=sorted(a),sorted(b)
if sum([a[i]!=b[i] for i in range(n+1)]):
	print("-1")
	exit()
f=dict()
def find(x):
	if f[x]==x:
		return x
	else:
		f[x]=find(f[x])
		return f[x]
ans=0
for i in range(n):
	if na[i]!=nb[i]:
		f[na[i]]=na[i]
f[a[n]]=a[n]
for i in range(n):
	if na[i]!=nb[i]:
		ans+=1
		f[find(nb[i])]=find(na[i])
for i,j in f:
	if i==j:
		ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
n,a,b,ax,bx=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0],0,0
na,nb=a,b
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
a,b=sorted(a),sorted(b)
if sum([a[i]!=b[i] for i in range(n+1)]):
	print("-1")
	exit()
mp=dict()
ax,bx=0,0
f=[i for i in range(n+1)]
def find(x):
	if f[x]==x:
		return x
	else:
		return find(f[x])
for i in range(n+1):
	mp[a[i]]=i
frog=True
for i in range(n):
	if na[i]!=nb[i]:
		frog=False
		f[find(mp[nb[i]])]=find(mp[na[i]])
if frog:
	print("0")
	exit()
st=set()
for i in range(n+1):
	st.add(find(mp[a[i]]))
print(n+len(st)-1)