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

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n,m=list(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)


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)


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 = list(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)


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()
#print(pts1)
#print(pts2)

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 # should not happen

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


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

#     Codeforces Round #488 by NEAR (Div. 2)
import collections
from functools import cmp_to_key
#key=cmp_to_key(lambda x,y: 1 if x not in y else -1 )

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))
#print(p1)

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

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

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

print(0)


n, m = list(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])
    return

#check fst
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)
        return

#check scd
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)
        return
print(0)
        



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
# print(dic1)
# print(dic2)
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)


#!/usr/bin/env python3

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




# Made By Mostafa_Khaled


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)


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

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