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: Wrong Answer

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)

    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])
        #print(ans)
    if sum(used)>1:
        ans += 1
    #if (bita==bitb and len(Da[bita])>1) or bita!=bitb:
    #    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: Wrong Answer

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)

    ans = -1
    used = [False]*(N+1)
    for i in range(N+1):
        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 or bita!=bitb:
        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: Wrong Answer

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)

    ans = -1
    used = [False]*(N+1)
    for i in range(N+1):
        if same[i]:
            continue
        p = uf.find(i)
        if used[p]:
            continue
        used[p] = True
        ans += (-uf.parent[p]+1)
        #print(ans)
    if (bita==bitb and len(Da[bita])>1) or bita!=bitb:
        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: Wrong Answer

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

    ans = -1
    used = [False]*(N+1)
    for i in range(N):
        if same[i]:
            continue
        p = uf.find(i)
        if used[p]:
            continue
        used[p] = True
        ans += (-uf.parent[p]+1)
        #print(ans)
    if (bita==bitb and len(Da[bita])>1) or bita!=bitb:
        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: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

bonusNumber = 0
for i in range(n):
    bonusNumber ^= a[i]

aa = Counter({bonusNumber: 1})
bb = Counter()

for i in range(n):
    aa[a[i]] += 1
    bb[b[i]] += 1

for x in bb.keys():
    if bb[x] > aa[x]:
        print(-1)
        exit()

#############################
ans = 0
tmp = []
first = True
for i in range(n):
    if first and b[i] == bonusNumber and b[i] != a[i]:
        bonusNumber = a[i]
        a[i] = b[i]
        ans += 1
        first = False
    elif b[i] != a[i]:
        tmp.append(b[i])

while bonusNumber in tmp:
    tmp.remove(bonusNumber)
    bonusNumber = a[b.index(bonusNumber)]
    ans += 1

if len(tmp) == 0:
    print(ans)
else:
    ans += len(tmp) + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if a == b:
	print(0)
	sys.exit()
if sorted(a) == sorted(b):
	res = 0
	for i in range(n):
		if a[i] != b[i]:
			res += 1
	print(res+1)
	sys.exit()
x = 0
for i in range(n):
	x ^= a[i]
#sa, sb = sorted(a), sorted(b)
ca, cb = Counter(a), Counter(b)
a_only, b_only = 0, 0
for k in ca.keys():
	if ca[k] > cb[k]:
		a_only += ca[k] - cb[k]
		only_a = k
for k in cb.keys():
	if cb[k] > ca[k]:
		b_only += cb[k] - ca[k]
		only_b = k

if a_only != 1 or b_only != 1:
	print(-1)
	sys.exit()
plus = False
res = 0
for i in range(n):
	if a[i] != b[i]:
		res += 1
		if a[i] == only_a and b[i] == only_b and cb[only_a] == 0:
			plus = True
print(res + plus)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if a == b:
	print(0)
	sys.exit()
if sorted(a) == sorted(b):
	res = 0
	for i in range(n):
		if a[i] != b[i]:
			res += 1
	print(res+1)
	sys.exit()
x = 0
for i in range(n):
	x ^= a[i]
#sa, sb = sorted(a), sorted(b)
ca, cb = Counter(a), Counter(b)
a_only, b_only = 0, 0
for k in ca.keys():
	if ca[k] > cb[k]:
		a_only += ca[k] - cb[k]
		only_a = k
for k in cb.keys():
	if cb[k] > ca[k]:
		b_only += cb[k] - ca[k]
		only_b = k

if a_only != 1 or b_only != 1:
	print(-1)
	sys.exit()
plus = False
res = 0
for i in range(n):
	if a[i] != b[i]:
		res += 1
		if a[i] == only_a and b[i] == only_b:
			plus = True
print(res + plus)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if a == b:
	print(0)
	sys.exit()
if sorted(a) == sorted(b):
	res = 0
	for i in range(n):
		if a[i] != b[i]:
			res += 1
	print(res+1)
	sys.exit()
x = 0
for i in range(n):
	x ^= a[i]
#sa, sb = sorted(a), sorted(b)
ca, cb = Counter(a), Counter(b)
a_only, b_only = 0, 0
for k in ca.keys():
	a_only += max(0, ca[k] - cb[k])
for k in cb.keys():
	b_only += max(0, cb[k] - ca[k])
if a_only != 1 or b_only != 1:
	print(-1)
	sys.exit()
res = 0
for i in range(n):
	if a[i] != b[i]:
		res += 1
print(res)

Submission status: Wrong Answer

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: Wrong Answer

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:
    print(len(b_))

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

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 if a0 == b0 else -1
    for a, b in zip(aaa, bbb):
        if a == b:
            continue
        ans += 1
        links[a].add(b)

    if not links:
        return 0

    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: Wrong Answer

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:
		f[x]=find(f[x])
		return f[x]
for i in range(n+1):
	mp[a[i]]=i
ed=0
for i in range(n):
	if na[i]!=nb[i]:
		ed+=1
		f[find(mp[nb[i]])]=find(mp[na[i]])
if ed==0:
	print("0")
	exit()
st=set()
for i in range(n+1):
	st.add(find(mp[a[i]]))
print(ed+len(st)-1)

Submission status: Wrong Answer

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:
		f[x]=find(f[x])
		return 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)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] = s1
            return True
        return False


def solve(a, b):
    axor, bxor = 0, 0
    for k in a:
        axor ^= k
    for k in b:
        bxor ^= k
    a += [axor]
    b += [bxor]
    if Counter(a) != Counter(b):
        return -1
    uft = UnionFind(n + 1)
    idx = defaultdict(set)
    same = 0

    for i, k in enumerate(a):
        idx[k].add(i)
    for i, k in enumerate(b):
        for j in idx[k]:
            if i == j:
                uft.table[i] = -2
                continue
            uft.union(i, j)
    return n - uft.table[:-1].count(-2) + max(0, uft.table[:-1].count(-1) - 1)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(solve(a, b))

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

from collections import Counter

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=0
for i in range(N):
    A^=a[i]
B=0
for i in range(N):
    B^=b[i]
a.append(A)
b.append(B)

if Counter(a)!=Counter(b):
    exit(print(-1))

val=set([])
for i in range(N+1):
    if a[i]!=b[i]:
        val.add(a[i])

if not val:
    exit(print(0))

val=list(val)
val.sort()
comp={i:e for e,i in enumerate(val)}
n=max(comp[d] for d in comp)+1

uf=UnionFindVerSize(n)
check=False
cnt=0
for i in range(N):
    if a[i]!=b[i]:
        uf.unite(comp[a[i]],comp[b[i]])
        if a[i]==b[-1]:
            check=True
        cnt+=1

print(cnt+uf.calc_group_num()-int(check))