Two participants are each given a pair of distinct numbers from 1 to 9 such that there's exactly one number that is present in both pairs. They want to figure out the number that matches by using a communication channel you have access to without revealing it to you.

Both participants communicated to each other a set of pairs of numbers, that includes the pair given to them. Each pair in the communicated sets comprises two different numbers.

Determine if you can with certainty deduce the common number, or if you can determine with certainty that both participants know the number but you do not.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 12$) — the number of pairs the first participant communicated to the second and vice versa.

The second line contains $n$ pairs of integers, each between $1$ and $9$, — pairs of numbers communicated from first participant to the second.

The third line contains $m$ pairs of integers, each between $1$ and $9$, — pairs of numbers communicated from the second participant to the first.

All pairs within each set are distinct (in particular, if there is a pair $(1,2)$, there will be no pair $(2,1)$ within the same set), and no pair contains the same number twice.

It is guaranteed that the two sets do not contradict the statements, in other words, there is pair from the first set and a pair from the second set that share exactly one number.


-----Output-----

If you can deduce the shared number with certainty, print that number.

If you can with certainty deduce that both participants know the shared number, but you do not know it, print $0$.

Otherwise print $-1$.


-----Examples-----
Input
2 2
1 2 3 4
1 5 3 4

Output
1

Input
2 2
1 2 3 4
1 5 6 4

Output
0

Input
2 3
1 2 4 5
1 2 1 3 2 3

Output
-1



-----Note-----

In the first example the first participant communicated pairs $(1,2)$ and $(3,4)$, and the second communicated $(1,5)$, $(3,4)$. Since we know that the actual pairs they received share exactly one number, it can't be that they both have $(3,4)$. Thus, the first participant has $(1,2)$ and the second has $(1,5)$, and at this point you already know the shared number is $1$.

In the second example either the first participant has $(1,2)$ and the second has $(1,5)$, or the first has $(3,4)$ and the second has $(6,4)$. In the first case both of them know the shared number is $1$, in the second case both of them know the shared number is $4$. You don't have enough information to tell $1$ and $4$ apart.

In the third case if the first participant was given $(1,2)$, they don't know what the shared number is, since from their perspective the second participant might have been given either $(1,3)$, in which case the shared number is $1$, or $(2,3)$, in which case the shared number is $2$. While the second participant does know the number with certainty, neither you nor the first participant do, so the output is $-1$.

Difficulty: HARD
Tags: Bit manipulation

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
[n, m] = list(map(int, input().strip().split()))
ais = list(map(int, input().strip().split()))
bis = list(map(int, input().strip().split()))
ais = [set(ais[2 * i:2 * i + 2]) for i in range(n)]
bis = [set(bis[2 * i:2 * i + 2]) for i in range(m)]

def check(pair, pairs):
	res = []
	for p in pairs:
		s = pair & p
		if len(s) == 1:
			res.append(s.pop())
	res = list(set(res))
	if len(res) == 1:
		return res[0]
	elif len(res) > 1:
		return -1
	else:
		return 0
va = [check(a, bis) for a in ais]
vb = [check(b, ais) for b in bis]
vap = [v for v in va if v > 0]
vbp = [v for v in vb if v > 0]
vap = set(vap)
vbp = set(vbp)
vabp = vap & vbp
if -1 in va or -1 in vb:
	print(-1)
elif len(vabp) > 1:
	print(0)
else:
	print(vabp.pop())


import sys
(na, nb) = list(map(int, sys.stdin.readline().split()))
(al, bl) = (list(map(int, sys.stdin.readline().split())), list(map(int, sys.stdin.readline().split())))
a = [set((al[2 * i], al[2 * i + 1])) for i in range(na)]
b = [set((bl[2 * i], bl[2 * i + 1])) for i in range(nb)]
(aposs, bposs) = (set(), set())
possible_shared = set()
(i_know_a_knows, i_know_b_knows) = (True, True)
for ahas in a:
	bposshere = set()
	for bp in b:
		if len(ahas & bp) == 1:
			bposshere |= ahas & bp
	possible_shared |= bposshere
	if len(bposshere) == 2:
		i_know_a_knows = False
for bhas in b:
	aposshere = set()
	for ap in a:
		if len(bhas & ap) == 1:
			aposshere |= bhas & ap
	possible_shared |= aposshere
	if len(aposshere) == 2:
		i_know_b_knows = False
if len(possible_shared) == 1:
	print(list(possible_shared)[0])
elif i_know_a_knows and i_know_b_knows:
	print(0)
else:
	print(-1)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
can0 = set()
can1 = [set() for i in range(n)]
can2 = [set() for i in range(m)]
for i in range(n):
	for j in range(m):
		x1 = a[i * 2]
		x2 = a[i * 2 + 1]
		y1 = b[j * 2]
		y2 = b[j * 2 + 1]
		if x1 > x2:
			(x1, x2) = (x2, x1)
		if y1 > y2:
			(y1, y2) = (y2, y1)
		if x1 == y1 and x2 == y2:
			continue
		if x1 == y1:
			can1[i].add(y1)
			can2[j].add(y1)
			can0.add(y1)
		if x2 == y1:
			can1[i].add(y1)
			can2[j].add(y1)
			can0.add(y1)
		if x1 == y2:
			can1[i].add(y2)
			can2[j].add(y2)
			can0.add(y2)
		if x2 == y2:
			can1[i].add(y2)
			can2[j].add(y2)
			can0.add(y2)
if len(can0) == 1:
	print(min(can0))
else:
	ok = True
	for i in can1:
		if len(i) > 1:
			ok = False
	for i in can2:
		if len(i) > 1:
			ok = False
	if ok:
		print(0)
	else:
		print(-1)


iter = 0
(n, m) = list(map(int, input().split()))
temppair = [0, 0]
i1 = list(map(int, input().split()))
i2 = list(map(int, input().split()))
l1 = []
l2 = []
d = 0
for i in i1:
	if d == 0:
		temppair[0] = i
		d = 1
	else:
		temppair[1] = i
		d = 0
		l1.append(sorted(temppair.copy()))
for i in i2:
	if d == 0:
		temppair[0] = i
		d = 1
	else:
		temppair[1] = i
		d = 0
		l2.append(sorted(temppair.copy()))
dic1 = dict()
dic2 = dict()
for i in range(len(l1)):
	l1[i] = (iter, l1[i])
	iter += 1
for i in range(len(l2)):
	l2[i] = (iter, l2[i])
	iter += 1
for e in l1:
	for e1 in l2:
		if (e[1][0] in e1[1] or e[1][1] in e1[1]) and e[1] != e1[1]:
			dic1[e[0]] = dic1.get(e[0], []) + [e1[1]]
for e in l2:
	for e1 in l1:
		if (e[1][0] in e1[1] or e[1][1] in e1[1]) and e[1] != e1[1]:
			dic2[e[0]] = dic2.get(e[0], []) + [e1[1]]
mybool = True
for (k, v) in list(dic1.items()):
	k = l1[k][1]
	mybool = mybool and (all([k[0] in p for p in v]) or all([k[1] in p for p in v]))
for (k, v) in list(dic2.items()):
	k = k - len(l1)
	k = l2[k][1]
	mybool = mybool and (all([k[0] in p for p in v]) or all([k[1] in p for p in v]))
c1 = True
dk1 = list(dic1)
dk1 = list([l1[k][1] for k in dk1])
sameone = dk1[0][0]
c1 = all([sameone in u for u in dk1])
for v in list(dic1.values()):
	c1 = c1 and all([sameone in u for u in v])
if not c1:
	c1 = True
	sameone = dk1[0][1]
	c1 = all([sameone in u for u in dk1])
	for v in list(dic1.values()):
		c1 = c1 and all([sameone in u for u in v])
if c1:
	(e, e1) = list(dic1.items())[0]
	e = l1[e][1]
	e1 = e1[0]
	if e[0] in e1:
		print(e[0])
		quit()
	else:
		print(e[1])
		quit()
elif mybool:
	print(0)
	quit()
else:
	print(-1)


(n, m) = list(map(int, input().split()))
p1 = list(map(int, input().split()))
p2 = list(map(int, input().split()))
cand = set()
cc = [set() for i in range(n)]
dd = [set() for i in range(m)]
for i in range(n):
	for j in range(m):
		(a, b) = (p1[2 * i], p1[2 * i + 1])
		(c, d) = (p2[2 * j], p2[2 * j + 1])
		if a not in (c, d) and b not in (c, d):
			continue
		if a in (c, d) and b in (c, d):
			continue
		if a in (c, d):
			kandidat = a
		else:
			kandidat = b
		cand.add(kandidat)
		cc[i].add(kandidat)
		dd[j].add(kandidat)
if len(cand) == 1:
	print(cand.pop())
elif max((len(cc[i]) for i in range(n))) <= 1 and max((len(dd[i]) for i in range(m))) <= 1:
	print(0)
else:
	print(-1)


(n, m) = map(int, input().split())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
a = []
b = []
for i in range(0, 2 * n, 2):
	a.append([aa[i], aa[i + 1]])
for i in range(0, 2 * m, 2):
	b.append([bb[i], bb[i + 1]])
accept = []
for num in range(1, 10):
	ina = []
	inb = []
	for x in a:
		if num in x:
			ina.append(x)
	for x in b:
		if num in x:
			inb.append(x)
	x = 0
	for t in ina:
		t.sort()
		for p in inb:
			p.sort()
			if t != p:
				x += 1
	if x > 0:
		accept.append(num)
if len(accept) == 1:
	print(accept[0])
	exit(0)
for t in a:
	z = set()
	for p in b:
		if t != p:
			if t[0] in p:
				z.add(t[0])
			if t[1] in p:
				z.add(t[1])
	if len(z) > 1:
		print(-1)
		exit(0)
for t in b:
	z = set()
	for p in a:
		if t != p:
			if t[0] in p:
				z.add(t[0])
			if t[1] in p:
				z.add(t[1])
	if len(z) > 1:
		print(-1)
		exit(0)
print(0)


def process(A, B):
	n = len(A)
	m = len(B)
	first = {}
	second = {}
	for i in range(0, n, 2):
		(a, b) = (A[i], A[i + 1])
		if a not in first:
			first[a] = set([])
		first[a].add(b)
		if b not in first:
			first[b] = set([])
		first[b].add(a)
	for i in range(0, m, 2):
		(a, b) = (B[i], B[i + 1])
		if a not in second:
			second[a] = set([])
		second[a].add(b)
		if b not in second:
			second[b] = set([])
		second[b].add(a)
	g = {}
	h = {}
	possible = set([])
	for i in range(10):
		if i in first and i in second:
			for j in range(10):
				if True:
					if j in first[i]:
						pair1 = (min(i, j), max(i, j))
						for j2 in second[i]:
							if j2 != j:
								pair2 = (min(i, j2), max(i, j2))
								if pair1 not in g:
									g[pair1] = set([])
								g[pair1].add(i)
								if pair2 not in h:
									h[pair2] = set([])
								h[pair2].add(i)
								possible.add(i)
					if j in second[i]:
						pair1 = (min(i, j), max(i, j))
						for j2 in first[i]:
							if j2 != j:
								pair2 = (min(i, j2), max(i, j2))
								if pair2 not in g:
									g[pair2] = set([])
								g[pair2].add(i)
								if pair1 not in h:
									h[pair1] = set([])
								h[pair1].add(i)
								possible.add(i)
	if len(possible) == 1:
		return list(possible)[0]
	one_knows = True
	for x in g:
		if len(g[x]) > 1:
			one_knows = False
	two_knows = True
	for x in h:
		if len(h[x]) > 1:
			two_knows = False
	if one_knows and two_knows:
		return 0
	else:
		return -1
(n, m) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
print(process(A, B))


def readpts():
	ip = list(map(int, input().split()))
	return [(min(ip[i], ip[i + 1]), max(ip[i], ip[i + 1])) for i in range(0, len(ip), 2)]
(N, M) = list(map(int, input().split()))
pts1 = readpts()
pts2 = readpts()

def psb(a, b):
	if a == b:
		return False
	return any((i in b for i in a))

def sb(a, b):
	for i in a:
		if i in b:
			return i
	return -1

def ipsv(pts1, pts2):
	ans = False
	for p1 in pts1:
		gsb = set()
		for p2 in pts2:
			if psb(p1, p2):
				gsb.add(sb(p1, p2))
		if len(gsb) > 1:
			return False
		if len(gsb) == 1:
			ans = True
	return ans

def sv():
	gsb = set()
	for p1 in pts1:
		for p2 in pts2:
			if psb(p1, p2):
				gsb.add(sb(p1, p2))
	if len(gsb) == 0:
		return -1
	if len(gsb) == 1:
		return list(gsb)[0]
	if ipsv(pts1, pts2) and ipsv(pts2, pts1):
		return 0
	return -1
print(sv())


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
possible1 = [set() for _ in range(200)]
possible2 = [set() for _ in range(200)]
weird = [0] * 15
p1 = list(map(int, input().split()))
p2 = list(map(int, input().split()))
for i in range(n):
	for j in range(m):
		a = sorted(p1[i * 2:i * 2 + 2])
		b = sorted(p2[j * 2:j * 2 + 2])
		if a == b:
			continue
		got = -1
		if a[0] in b:
			got = a[0]
		if a[1] in b:
			got = a[1]
		if got == -1:
			continue
		weird[got] = 1
		possible1[a[0] * 11 + a[1]].add(got)
		possible2[b[0] * 11 + b[1]].add(got)
if sum(weird) == 1:
	print(weird.index(1))
elif max((len(i) for i in possible1)) == 1 and max((len(i) for i in possible2)) == 1:
	print(0)
else:
	print(-1)


q = input()
q1 = input().split()
q2 = input().split()
parr1 = []
for i in range(0, len(q1), 2):
	pair = (q1[i], q1[i + 1])
	parr1.append(pair)
parr2 = []
for i in range(0, len(q2), 2):
	pair = (q2[i], q2[i + 1])
	parr2.append(pair)
matches1 = {}
matches2 = {}
for i in parr1:
	for j in parr2:
		if i[0] == j[0] and i[1] == j[1] or (i[0] == j[1] and i[1] == j[0]):
			continue
		elif i[0] == j[0] or i[0] == j[1]:
			if matches1.get(i) == None or matches1.get(i) == i[0]:
				matches1[i] = i[0]
			else:
				print('-1')
				quit()
			if matches2.get(j) == None or matches2.get(j) == i[0]:
				matches2[j] = i[0]
			else:
				print('-1')
				quit()
		elif i[1] == j[1] or i[1] == j[0]:
			if matches1.get(i) == None or matches1.get(i) == i[1]:
				matches1[i] = i[1]
			else:
				print('-1')
				quit()
			if matches2.get(j) == None or matches2.get(j) == i[1]:
				matches2[j] = i[1]
			else:
				print('-1')
				quit()
		else:
			pass
matches = list(matches1.values())
for i in range(0, len(matches)):
	if matches[i] == matches[i - 1]:
		pass
	else:
		print('0')
		quit()
print(matches[0])


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
for _ in range(t):
	(n, m) = map(int, input().split())
	a1 = list(map(int, input().split()))
	b1 = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append([a1[2 * i], a1[2 * i + 1]])
	b = []
	for i in range(m):
		b.append([b1[2 * i], b1[2 * i + 1]])
	candidates = set()
	neg = 0
	neg1 = 0
	for i in range(n):
		(x, y) = a[i]
		possible = set()
		for j in range(m):
			(p, q) = b[j]
			if (x == p or x == q) and (y != p and y != q):
				possible.add(x)
			if (y == p or y == q) and (x != p and x != q):
				possible.add(y)
		if len(possible) > 1:
			neg = 1
		candidates = candidates.union(possible)
	for i in range(m):
		(x, y) = b[i]
		possible = set()
		for j in range(n):
			(p, q) = a[j]
			if (x == p or x == q) and (y != p and y != q):
				possible.add(x)
			if (y == p or y == q) and (x != p and x != q):
				possible.add(y)
		if len(possible) > 1:
			neg = 1
	if len(candidates) == 1:
		print(candidates.pop())
	elif neg:
		print(-1)
	else:
		print(0)


import collections
from functools import cmp_to_key
import sys

def getIntList():
	return list(map(int, input().split()))
import bisect

def makePair(z):
	return [(z[i], z[i + 1]) for i in range(0, len(z), 2)]
(N, M) = getIntList()
p1 = getIntList()
p1 = makePair(p1)
p1 = list(map(set, p1))
p2 = getIntList()
p2 = makePair(p2)
p2 = list(map(set, p2))
res = set()
for x in p1:
	for y in p2:
		z = x & y
		if len(z) == 2 or len(z) == 0:
			continue
		res = res | z
if len(res) == 1:
	print(res.pop())
	sys.exit()
for x in p1:
	nz = set()
	for y in p2:
		z = x & y
		if len(z) == 2 or len(z) == 0:
			continue
		nz = nz | z
	if len(nz) == 2:
		print(-1)
		sys.exit()
for x in p2:
	nz = set()
	for y in p1:
		z = x & y
		if len(z) == 2 or len(z) == 0:
			continue
		nz = nz | z
	if len(nz) == 2:
		print(-1)
		sys.exit()
print(0)


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
(p1, p2) = ([], [])
challengers = list(map(int, stdin.readline().split()))
for i in range(n):
	p1.append((challengers[i * 2], challengers[i * 2 + 1]))
challengers = list(map(int, stdin.readline().split()))
for i in range(m):
	p2.append((challengers[i * 2], challengers[i * 2 + 1]))
label = -1
X = 10
count = [0 for i in range(X)]
for x in range(1, X):
	for i in range(n):
		if x not in p1[i]:
			continue
		for j in range(m):
			if x not in p2[j]:
				continue
			if len(set(p1[i]) & set(p2[j])) == 1:
				count[x] += 1
				c = x
if count.count(0) == 9:
	stdout.write(str(c))
else:
	label = 1
	ind = 0
	for p11 in p1:
		cur = set()
		for p22 in p2:
			if len(set(p11) & set(p22)) == 1:
				cur |= set(p11) & set(p22)
		if len(cur) == 2:
			label = 0
	for p22 in p2:
		cur = set()
		for p11 in p1:
			if len(set(p11) & set(p22)) == 1:
				cur |= set(p11) & set(p22)
		if len(cur) == 2:
			label = 0
	if label == 1:
		stdout.write('0')
	else:
		stdout.write('-1')


from itertools import product, combinations

def main():
	(n, m) = map(int, input().split())
	aa = list(map(int, input().split()))
	bb = list(map(int, input().split()))
	a2 = [set(aa[i:i + 2]) for i in range(0, n * 2, 2)]
	b2 = [set(bb[i:i + 2]) for i in range(0, m * 2, 2)]
	(seeds, l) = (set(aa) & set(bb), [])
	for s in seeds:
		canda = {d for a in a2 for d in a if s in a and d != s}
		candb = {d for b in b2 for d in b if s in b and d != s}
		for (a, b) in product(canda, candb):
			if a != b:
				l.append((s, a, b))
	print(l[0][0] if len(set((t[0] for t in l))) == 1 else -any((a[:2] == b[-2::-1] or a[::2] == b[-1::-2] for (a, b) in combinations(l, 2))))
main()


def rp():
	cs = list(map(int, input().split(' ')))
	cs = list(zip(cs[0::2], cs[1::2]))
	return cs

def dist(p1, p2):
	return len(set(p1).union(set(p2))) - 2
input()
ps = [rp(), rp()]
theyCan = True
myPos = set()
for (ps1, ps2) in [ps, ps[::-1]]:
	for p1 in ps1:
		pos = set()
		for p2 in ps2:
			if dist(p1, p2) == 1:
				pos = pos.union(set(p1).intersection(set(p2)))
		if len(pos) >= 2:
			theyCan = False
		myPos = myPos.union(pos)
print(next(iter(myPos)) if len(myPos) == 1 else 0 if theyCan else -1)