Zane the wizard is going to perform a magic show shuffling the cups.

There are n cups, numbered from 1 to n, placed along the x-axis on a table that has m holes on it. More precisely, cup i is on the table at the position x = i.

The problematic bone is initially at the position x = 1. Zane will confuse the audience by swapping the cups k times, the i-th time of which involves the cups at the positions x = u_{i} and x = v_{i}. If the bone happens to be at the position where there is a hole at any time, it will fall into the hole onto the ground and will not be affected by future swapping operations.

Do not forget that Zane is a wizard. When he swaps the cups, he does not move them ordinarily. Instead, he teleports the cups (along with the bone, if it is inside) to the intended positions. Therefore, for example, when he swaps the cup at x = 4 and the one at x = 6, they will not be at the position x = 5 at any moment during the operation. [Image] 

Zane’s puppy, Inzane, is in trouble. Zane is away on his vacation, and Inzane cannot find his beloved bone, as it would be too exhausting to try opening all the cups. Inzane knows that the Codeforces community has successfully helped Zane, so he wants to see if it could help him solve his problem too. Help Inzane determine the final position of the bone.


-----Input-----

The first line contains three integers n, m, and k (2 ≤ n ≤ 10^6, 1 ≤ m ≤ n, 1 ≤ k ≤ 3·10^5) — the number of cups, the number of holes on the table, and the number of swapping operations, respectively.

The second line contains m distinct integers h_1, h_2, ..., h_{m} (1 ≤ h_{i} ≤ n) — the positions along the x-axis where there is a hole on the table.

Each of the next k lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the positions of the cups to be swapped.


-----Output-----

Print one integer — the final position along the x-axis of the bone.


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

Output
1
Input
5 1 2
2
1 2
2 4

Output
2


-----Note-----

In the first sample, after the operations, the bone becomes at x = 2, x = 5, x = 7, and x = 1, respectively.

In the second sample, after the first operation, the bone becomes at x = 2, and falls into the hole onto the ground.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin, stdout

n, m, k = map(int, stdin.readline().split())
position = set(list(map(int, stdin.readline().split())))

start = 1
for i in range(k):
    if start in position:
        break
    else:
        a, b = map(int, stdin.readline().split())
        if a == start:
            start = b
        elif b == start:
            start = a

stdout.write(str(start))

(n, m, k) = list(map(int, input().split(' ')))
hs = list(map(int, input().split(' ')))

holes = set(hs)

pos = 1

for i in range(k):
    if pos in holes:
        break
    (u, v) = list(map(int, input().split(' ')))
    if pos == u:
        pos = v
    elif pos == v:
        pos = u

print(pos)



#!/usr/bin/env python3


def solve():
    n, m, k = list(map(int, input().split()))
    h = set(map(int, input().split()))

    pos = 1

    for i in range(k):
        u, v = list(map(int, input().split()))
        if pos != u:
            u, v = v, u
        if pos == u:
            if u not in h:
                pos = v

    print(pos)


def __starting_point():
    solve()

__starting_point()

import sys
n, m, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
b = [0] * n
for i in a:
    b[i] = 1
now = 0
for i in range(k):
    if b[now]:
        print(now + 1)
        return    
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if now == x:
        now = y
    elif now == y:
        now = x
    
print(now + 1)

n,m,k=map(int,input().split())
l=set(map(int,input().split()))
i=1
for _ in range(k):
    u,v=map(int,input().split())
    if i in l: break
    if i==u: i=v
    elif i==v: i=u
print(i)

n, m, k = list(map(int, input().split()))
H = set(map(int, input().split()))

bone_pos = 1

if bone_pos not in H:
    for i in range(k):
        u, v = list(map(int, input().split()))
        if bone_pos == u:
            bone_pos = v
        elif bone_pos == v:
            bone_pos = u

        if bone_pos in H:
            break

print(bone_pos)


import sys

def solve():
    n, m, k = map(int, sys.stdin.readline().split())
    h = [int(i) - 1 for i in sys.stdin.readline().split()]

    is_hole = [False] * n
    for hi in h:
        is_hole[hi] = True

    pos = 0

    if is_hole[pos]:
        print(pos + 1)
        return

    for i in range(k):
        u, v = map(int, sys.stdin.readline().split())
        u, v = u-1, v-1

        if u != pos and v != pos:
            continue

        if u != pos:
            pos = u
        elif v != pos:
            pos = v

        if is_hole[pos]:
            print(pos + 1)
            return

    print(pos + 1)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def __starting_point():
    solve()
__starting_point()

n, m, k = list(map(int, input().split()))
holes = list(map(int, input().split()))

is_hole = [False for i in range(n)]

for i in holes:
    is_hole[i - 1] = True

bone = 0

if is_hole[0]:
    print(1)
else:
    was = False
    for i in range(k):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        if a == bone:
            bone = b
        elif b == bone:
            bone = a
        if is_hole[bone]:
            was = True
            print(bone + 1)
            break
    if not was:
        print(bone + 1)


n, m, k = list(map(int, input().split()))
otv = set(input().split())
x = '1'
for _ in range(k):
    if x in otv:
        break
    o, p = input().split()
    if x == o:
        x = p
    elif x == p:
        x = o
print(x)


n,m,k=list(map(int,input().split()))
h={int(x) for x in input().split()}
p=1
for t in range(k):
  u,v=list(map(int,input().split()))
  if p in h: break
  elif p==u: p=v
  elif p==v: p=u

print(p)


n, m, k = list(map(int, input().split()))
d = {}
if m > 0:
    for x in map(int, input().split()):
        d[x] = True
ball = 1
for i in range(k):
    if ball in d:
        break
    x, y = list(map(int, input().split()))
    ball = x if ball == y else y if ball == x else ball
print(ball)


from sys import stdin

n, m, k = list(map(int, stdin.readline().split()))
holes = set(map(int, stdin.readline().split()))

pos = 1
if pos not in holes:
    for i in range(k):
        u, v = list(map(int, stdin.readline().split()))
        if u == pos:
            pos = v
            if pos in holes:
                break
        elif v == pos:
            pos = u
            if pos in holes:
                break

print(pos)


#!/usr/bin/env python3
from sys import stdin,stdout


def ri():
    return list(map(int, stdin.readline().split()))

n, m, k = ri()
h = [0 for i in range(n+1)]
hh = list(ri())
for i in range(m):
    h[hh[i]] = 1
p = 1
for i in range(k):
    if h[p] == 1:
        print(p)
        return
    a, b = ri()
    if p in [a, b]:
        if a == p:
            p = b
        else:
            p = a

print(p)




n,m,k = list(map(int,input().split()))
hole = set(map(int,input().split()))
fall = 0
current = 1
for i in range(k):
	if fall == 0 and current in hole:
		fall = current
	u,v = list(map(int,input().split()))
	if u == current:
		current = v
	elif v == current:
		current = u
if fall != 0:
	print(fall)
else:
	print(current)



n,m,k = list(map(int,input().split()))
hole = [False for _ in range(n)]
for h in input().split():
    hh = int(h)-1
    hole[hh] = True

bone = 0
fallen = hole[0]

for _ in range(k):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    if not fallen:
        if bone == a:
            bone = b
        elif bone == b:
            bone = a
        fallen = hole[bone]

print(bone+1)


iters = int(input().split()[2])

holes = {int(x) for x in input().split()}

current = 1

for _ in range(iters):
    src, dest = (int(x) for x in input().split())
    if current in holes:
        break
    if current == src:
        current = dest
    elif current == dest:
        current = src
print(current)

a,b,c = list(map(int,input().split()))
s = set(map(int,input().split()))
ans = 1
if ans not in s:
    for i in range(0,c):
        x,y = list(map(int,input().split()))
        if ans==x:
            ans=y
        elif ans==y:
            ans=x
        if ans in s:
            break
print(ans)


import sys
    
n, m, k = list(map(int, sys.stdin.readline().strip().split(" ")))

holes = set(map(int, sys.stdin.readline().strip().split(" ")))
    
pos = 1
for i in range(k):
    u, v = list(map(int, sys.stdin.readline().strip().split(" ")))
        
    if pos not in holes:        
        if pos == u:
            pos = v
        elif pos == v:
            pos = u
                
print(pos)


from bisect import bisect_left

n,m,k = map(int, input().split(' '))
holes = list(map(int, input().split(' ')))
curr = 1
found = False

holes = sorted(holes)
H = len(holes)


def bins(x, bot, top=None):
    top = top if top is not None else H
    pos = bisect_left(holes, x, bot, top)
    return pos != top and holes[pos] == x


if curr in holes:
    print(curr)
    found = True
else:
    for a0 in range(k):
        u, v = map(int, input().split(' '))
        if u == curr:
            curr = v
            if bins(curr, 0):
                print(curr)
                found = True
                break
        elif v == curr:
            curr = u
            if bins(curr, 0):
                print(curr)
                found = True
                break

if not found:
    print(curr)

n, m, k = [int(s) for s in input().split(" ")]
hole_locations = [int(s) for s in input().split(" ")]
# print(hole_locations)
hole_array = [0] * n
for hole in hole_locations:
    hole_array[hole-1] += 1
# print(hole_array)
# location of bone
bone = 1
if hole_array[0] == 1:
    print(bone)
else:
    for i in range(1, k + 1):
      # swaps.append([int(s) for s in input().split(" ")])
      u, v = [int(s) for s in input().split(" ")]
      if u == bone:
          bone = v
          if hole_array[v-1] == 1:
              break
      elif v == bone:
          bone = u
          if hole_array[u-1] == 1:
              break
    print(bone)

n, m, k = map(int, input().split())

h = set(map(int, input().split()))
answer = 1
if answer in h:
    print(answer)
else:
    for i in range(k):
        u, v = map(int, input().split())
        if u == answer:
            answer = v
        elif v == answer:
            answer = u
        else:
            continue
        if answer in h:
            break
    print(answer)

n, m, k = map(int, input().split())
data = set(map(int, input().split()))
cur = 1
for i in range(k):
  if cur in data: break
  u, v = map(int, input().split())
  if u == cur: cur = v
  elif v == cur: cur = u
print(cur)

n,m,k=list(map(int,input().split()))
ip=list(map(int,input().split()))
holes=[0 for i in range(n+1)]
for i in ip:
    holes[i]=1
pos=1
b=0
if holes[1]==1:
    b=1
for i in range(k):
    u,v=list(map(int,input().split()))
    if u==pos and b==0:
        pos=v
        if holes[v]==1:
            b=1
    elif v==pos and b==0:
        pos=u
        if holes[u]==1:
            b=1
print(pos)


n,m,k=map(int,input().split())
h=set([i for i in input().split()])
ans=chk='1'

while k:
    k=k-1
    if ans in h:
        break
    x,y=map(str,input().split())
    if x==ans:
        ans=y
    elif y==ans:
        ans=x
print(ans)

n, m, k = [int(x) for x in input().strip().split(' ')]
holes = set([int(x) for x in input().strip().split(' ')])
bone = 1
fall = bone in holes
i = 0
while i < k and not fall:
    a, b = [int(x) for x in input().strip().split(' ')]
    if a == bone:
        bone = b
    elif b == bone:
        bone = a
    fall = bone in holes
    i += 1

print(bone)