Bessie is out grazing on the farm, which consists of $n$ fields connected by $m$ bidirectional roads. She is currently at field $1$, and will return to her home at field $n$ at the end of the day.

The Cowfederation of Barns has ordered Farmer John to install one extra bidirectional road. The farm has $k$ special fields and he has decided to install the road between two different special fields. He may add the road between two special fields that already had a road directly connecting them.

After the road is added, Bessie will return home on the shortest path from field $1$ to field $n$. Since Bessie needs more exercise, Farmer John must maximize the length of this shortest path. Help him!


-----Input-----

The first line contains integers $n$, $m$, and $k$ ($2 \le n \le 2 \cdot 10^5$, $n-1 \le m \le 2 \cdot 10^5$, $2 \le k \le n$)  — the number of fields on the farm, the number of roads, and the number of special fields.

The second line contains $k$ integers $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$)  — the special fields. All $a_i$ are distinct.

The $i$-th of the following $m$ lines contains integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), representing a bidirectional road between fields $x_i$ and $y_i$.

It is guaranteed that one can reach any field from every other field. It is also guaranteed that for any pair of fields there is at most one road connecting them.


-----Output-----

Output one integer, the maximum possible length of the shortest path from field $1$ to $n$ after Farmer John installs one road optimally.


-----Examples-----

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


-----Note-----

The graph for the first example is shown below. The special fields are denoted by red. It is optimal for Farmer John to add a road between fields $3$ and $5$, and the resulting shortest path from $1$ to $5$ is length $3$.

The graph for the second example is shown below. Farmer John must add a road between fields $2$ and $4$, and the resulting shortest path from $1$ to $5$ is length $3$.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Sorting

Greedy algorithms

Data structures
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
from sys import stdin, stdout
from os import path
from collections import deque
from heapq import heappop, heappush
maxn = 200005
mark = [0 for i in range(maxn)]
f = [0 for i in range(maxn)]
g = [0 for i in range(maxn)]
a = [[] for i in range(maxn)]
ans = 0

def bfs(s, f):
	global a
	q = deque()
	q.append(s)
	while len(q) > 0:
		u = q.popleft()
		for v in a[u]:
			if v == s:
				continue
			if not f[v]:
				f[v] = f[u] + 1
				q.append(v)
if path.exists('inp.txt'):
	stdin = open('inp.txt', 'r')
(n, m, k) = map(int, stdin.readline().split())
p = list(map(int, stdin.readline().split()))
for i in p:
	mark[i] = 1
for i in range(m):
	(u, v) = map(int, stdin.readline().split())
	a[u].append(v)
	a[v].append(u)
bfs(1, f)
bfs(n, g)
node = []
for i in range(1, n + 1):
	if mark[i]:
		node.append((f[i], g[i]))
node.sort()
pq = []
for i in range(len(node)):
	heappush(pq, (-node[i][1], i))
for i in range(len(node)):
	while len(pq) > 0:
		u = heappop(pq)
		if u[1] <= i:
			continue
		else:
			heappush(pq, u)
			break
	if not len(pq):
		continue
	tmp = heappop(pq)
	heappush(pq, tmp)
	u = node[i]
	v = node[tmp[1]]
	res = min(u[0] + v[1], u[1] + v[0]) + 1
	res = min(res, min(u[0] + u[1], v[0] + v[1]))
	ans = max(ans, res)
stdout.write(str(min(ans, f[n])))


import sys
from collections import deque
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(k):
	a[i] -= 1
g = [[] for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)

def bfs(s):
	dist = [10 ** 18] * n
	dist[s] = 0
	dq = deque()
	dq.append([-1, s])
	while dq:
		(par, ver) = dq.popleft()
		for to in g[ver]:
			if par != to and dist[to] > dist[ver] + 1:
				dist[to] = dist[ver] + 1
				dq.append([ver, to])
	return dist
d0 = bfs(0)
d1 = bfs(n - 1)
l = []
for aa in a:
	l.append([d0[aa] - d1[aa], aa])
l.sort()
ans = 0
max_x = -10 ** 18
for i in range(len(l)):
	ans = max(ans, max_x + d1[l[i][1]])
	max_x = max(max_x, d0[l[i][1]])
print(min(ans + 1, d0[n - 1]))


import sys
import collections
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
(n, m, k) = ints()
special = ints()
graph = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = ints()
	graph[x].append(y)
	graph[y].append(x)
d1 = [-1 for _ in range(n + 1)]
q = collections.deque([1])
depth = 1
d1[1] = 0
while q:
	for _ in range(len(q)):
		node = q.popleft()
		for nb in graph[node]:
			if d1[nb] == -1:
				q.append(nb)
				d1[nb] = depth
	depth += 1
d2 = [-1 for _ in range(n + 1)]
q = collections.deque([n])
depth = 1
d2[n] = 0
while q:
	for _ in range(len(q)):
		node = q.popleft()
		for nb in graph[node]:
			if d2[nb] == -1:
				q.append(nb)
				d2[nb] = depth
	depth += 1
ans = d2[1]
s_distances = [(d1[i], d2[i]) for i in special]
s_distances.sort(key=lambda x: x[1], reverse=True)
mx = 0
for i in range(len(s_distances) - 1):
	l = s_distances[i + 1][1] + 1 + s_distances[i][0]
	mx = max(mx, l)
print(min(ans, mx))


import sys
from collections import deque
from functools import cmp_to_key
INF = 1000000000.0 + 6
input = sys.stdin.readline

def compareeee(x, y):
	if X[x] + Y[y] > X[y] + Y[x]:
		return 1
	elif X[x] + Y[y] < X[y] + Y[x]:
		return -1
	else:
		return 0

def comparee(x, y):
	return X[x] + Y[y] > Y[x] + X[y]

def bfs(v, x):
	q = deque()
	if x == 0:
		X[v] = 0
	else:
		Y[v] = 0
	q.append(v)
	while len(q) > 0:
		u = q.popleft()
		for xx in G[u]:
			if x == 0:
				if X[xx] > X[u] + 1:
					X[xx] = X[u] + 1
					q.append(xx)
			elif Y[xx] > Y[u] + 1:
				Y[xx] = Y[u] + 1
				q.append(xx)
(n, m, k) = map(int, input().split())
G = [[] for _ in range(n)]
X = [INF for i in range(n)]
Y = [INF for i in range(n)]
tmp = 0
a = list(map(lambda x: int(x) - 1, input().split()))
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	G[v].append(u)
	G[u].append(v)
bfs(0, 0)
bfs(n - 1, 1)
both = []
for x in a:
	both.append([-X[x] + Y[x], X[x], Y[x]])
both.sort()
ans = 0
yArray = -INF
for i in range(k):
	ans = max(ans, both[i][1] + yArray)
	yArray = max(yArray, both[i][2])
print(min(X[n - 1], ans + 1))


import sys
from operator import itemgetter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(N, nodes, src):
	from collections import deque
	que = deque([(src, 0)])
	dist = [INF] * N
	while que:
		(u, c) = que.popleft()
		if dist[u] != INF:
			continue
		dist[u] = c
		for v in nodes[u]:
			que.append((v, c + 1))
	return dist
(N, M, K) = MAP()
S = set((a - 1 for a in LIST()))
nodes = [[] for i in range(N)]
for _ in range(M):
	(a, b) = MAP()
	a -= 1
	b -= 1
	nodes[a].append(b)
	nodes[b].append(a)
dist1 = bfs(N, nodes, 0)
dist2 = bfs(N, nodes, N - 1)
mn = dist1[N - 1]
AB = []
for i in range(N):
	(a, b) = (dist1[i], dist2[i])
	if i in S:
		AB.append((a - b, a, b))
AB.sort(key=itemgetter(0))
(_, A, B) = zip(*AB)
ans = 0
mx = A[0]
for i in range(1, K):
	(a, b) = (A[i], B[i])
	ans = max(ans, mx + b + 1)
	mx = max(mx, a)
ans = min(ans, mn)
print(ans)


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time

def I():
	return int(input())

def MI():
	return map(int, input().split())

def S():
	return input()

def MS():
	return map(str, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def StoI():
	return [ord(i) - 97 for i in input()]

def ItoS(nn):
	return chr(nn + 97)

def input():
	return sys.stdin.readline().rstrip()

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = {False: 'No', True: 'Yes'}
MOD = 10 ** 9 + 7
inf = float('inf')
IINF = 10 ** 10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False

def bfs(graph, initial, n):
	dist = [-1] * (n + 1)
	q = deque([initial])
	visited = [False] * (n + 1)
	visited[initial] = True
	dist[initial] = 0
	while len(q) != 0:
		edge = q.popleft()
		nxt = graph[edge]
		for (i, e) in enumerate(nxt):
			if visited[e] is False:
				q.append(e)
				dist[e] = dist[edge] + 1
				visited[e] = True
	return dist

def main():
	(n, m, k) = MI()
	a = LI()
	graph = [[] for i in range(n + 1)]
	is_special = {}
	for i in a:
		is_special[i] = True
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	dist_1toN = bfs(graph, 1, n)
	dist_Nto1 = bfs(graph, n, n)
	data = [None] * k
	for i in range(len(a)):
		x = dist_1toN[a[i]]
		y = dist_Nto1[a[i]]
		data[i] = (x - y, a[i])
	data.sort()
	a = [d[1] for d in data]
	best = 0
	maxv = -10 ** 9
	for i in range(len(a)):
		best = max(best, maxv + dist_Nto1[a[i]])
		maxv = max(maxv, dist_1toN[a[i]])
	print(min(dist_1toN[n], best + 1))
main()


from sys import stdin, gettrace
from collections import deque
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():
	(n, m, k) = map(int, input().split())
	aa = [int(a) - 1 for a in input().split()]
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		adj[x - 1].append(y - 1)
		adj[y - 1].append(x - 1)

	def getdists(f):
		dist = [-1] * n
		dq = deque([f])
		dist[f] = 0
		while dq:
			p = dq.popleft()
			for c in adj[p]:
				if dist[c] == -1:
					dist[c] = dist[p] + 1
					dq.append(c)
		return dist
	dist1 = getdists(0)
	distn = getdists(n - 1)
	base = dist1[n - 1]
	diffdist = [(dist1[a] - distn[a], a) for a in aa]
	diffdist.sort()
	mx1 = -n
	mxt = 0
	for (_, a) in diffdist:
		mxt = max(mxt, distn[a] + mx1 + 1)
		mx1 = max(mx1, dist1[a])
		if mxt > base:
			mxt = base
			break
	print(mxt)
main()


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	(N, M, K) = getInts()
	A = set(getInts())
	G = [[] for _ in range(N)]
	for i in range(M):
		(u, v) = getInts()
		u -= 1
		v -= 1
		G[u].append(v)
		G[v].append(u)
	used = [0] * N
	depth = [0] * N
	Q = dq([(0, 0)])
	used[0] = 1
	while Q:
		(node, level) = Q.popleft()
		for neigh in G[node]:
			if not used[neigh]:
				used[neigh] = 1
				depth[neigh] = level + 1
				Q.append((neigh, level + 1))
	usedN = [0] * N
	depthN = [0] * N
	Q = dq([(N - 1, 0)])
	usedN[N - 1] = 1
	while Q:
		(node, level) = Q.popleft()
		for neigh in G[node]:
			if not usedN[neigh]:
				usedN[neigh] = 1
				depthN[neigh] = level + 1
				Q.append((neigh, level + 1))
	diff = [(depth[i - 1] - depthN[i - 1], i - 1) for i in A]
	diff.sort()
	ans = 0
	max_ = -10 ** 18
	for i in range(len(diff)):
		a = diff[i][1]
		ans = max(ans, max_ + depthN[a])
		max_ = max(max_, depth[a])
	return min(depth[N - 1], ans + 1)
print(solve())


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
l = [c - 1 for c in l]
edge = [[] for _ in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	edge[x].append(y)
	edge[y].append(x)
from collections import deque

def bfs(edge, start):
	q = deque()
	visit = [-1] * n
	q.append(start)
	visit[start] = 0
	while q:
		x = q.popleft()
		for new_x in edge[x]:
			if visit[new_x] == -1:
				visit[new_x] = visit[x] + 1
				q.append(new_x)
	return visit
dist0 = bfs(edge, 0)
dist1 = bfs(edge, n - 1)
d = [[0, 0, 0] for _ in range(k)]
for i in range(k):
	d[i][0] = dist0[l[i]]
	d[i][1] = dist1[l[i]]
	d[i][2] = dist0[l[i]] - dist1[l[i]]
d.sort(key=lambda x: x[2])
max_x = -float('inf')
ans = 0
for i in range(k):
	ans = max(ans, max_x + d[i][1])
	max_x = max(max_x, d[i][0])
print(min(ans + 1, dist0[-1]))


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	(n, m, k) = geti()
	a = getl()
	edges = dd(list)
	for i in range(m):
		(u, v) = geti()
		edges[u].append(v)
		edges[v].append(u)
	vis = dd(int)
	dist = [[inf] * (n + 1) for _ in range(2)]

	def bfs(root, index):
		q = deque()
		q.append((root, 0))
		vis[root] = True
		while q:
			(now, cost) = q.popleft()
			dist[index][now] = cost
			for node in edges[now]:
				if node not in vis:
					vis[node] = True
					q.append((node, cost + 1))
	bfs(1, 0)
	vis.clear()
	bfs(n, 1)
	need = sorted(a, key=lambda x: dist[0][x])
	ans = -inf
	for i in range(1, len(need)):
		left = dist[0][need[i - 1]]
		right = dist[1][need[i]]
		let = left + right + 1
		left = dist[0][need[i]]
		right = dist[1][need[i - 1]]
		ans = max(ans, min(let, left + right + 1))
	print(min(ans, dist[0][n]))
solve()


import sys
input = sys.stdin.readline
(n, m, K) = map(int, input().split())
sp = list(map(lambda x: int(x) - 1, input().split()))
peer = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	peer[a].append(b)
	peer[b].append(a)
a0 = [10 ** 6 for _ in range(n)]
a0[0] = 0
a1 = [10 ** 6 for _ in range(n)]
a1[-1] = 0
now = [0]
while now:
	last = now
	now = []
	for x in last:
		for y in peer[x]:
			if a0[y] > a0[x] + 1:
				a0[y] = a0[x] + 1
				now.append(y)
now = [n - 1]
while now:
	last = now
	now = []
	for x in last:
		for y in peer[x]:
			if a1[y] > a1[x] + 1:
				a1[y] = a1[x] + 1
				now.append(y)
xyxy = []
for w in sp:
	xyxy.append([a0[w] - a1[w], a0[w], a1[w]])
xyxy.sort()
xx = []
maxi = 0
for j in range(K):
	xx.append(max(maxi, xyxy[j][1]))
can = []
for j in range(1, K):
	can.append(xx[j - 1] + xyxy[j][2] + 1)
print(min(a0[-1], max(can)))


from collections import deque
import sys

def bfs(s):
	q = deque()
	d = [-1] * n
	q.append(s)
	d[s] = 0
	while len(q) > 0:
		u = q.popleft()
		for v in adj[u]:
			if d[v] == -1:
				d[v] = d[u] + 1
				q.append(v)
	return d
(n, m, k) = map(int, input().split())
a = list(map(lambda x: x - 1, map(int, input().split())))
inp = sys.stdin.readlines()
adj = [[] for _ in range(n)]
for i in range(m):
	(x, y) = map(int, inp[i].split())
	x -= 1
	y -= 1
	adj[x].append(y)
	adj[y].append(x)
ds = bfs(0)
de = bfs(n - 1)
p = sorted([(ds[i], de[i]) for i in a])
mx = p[0][0]
ans = 0
for i in range(1, k):
	ans = max(mx + p[i][1] + 1, ans)
	mx = max(mx, p[i][0])
print(min(ans, de[0]))


from collections import deque
import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
sp = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n + 1)]
for (a, b) in ab:
	graph[a].append(b)
	graph[b].append(a)
vf1 = [0 for i in range(n + 1)]
vfn = [0 for i in range(n + 1)]

def bfs(x, vf):
	que = deque([(x, 1)])
	while que:
		(x, cnt) = que.popleft()
		vf[x] = cnt
		for y in graph[x]:
			if vf[y] == 0:
				que.append((y, cnt + 1))
				vf[y] = cnt + 1
bfs(1, vf1)
bfs(n, vfn)
ans = vf1[n] - 1
ansls = []
for i in sp:
	ansls.append((vf1[i], vfn[i]))
ansls.sort(reverse=True)
l = len(ansls)
mx = ansls[0][1]
anstmp = []
for i in range(1, l):
	mx = max(mx, ansls[i - 1][1])
	anstmp.append(ansls[i][0] + mx - 1)
print(min(ans, max(anstmp)))


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

class SegmentTree:

	def __init__(self, N, operator, identity_element):
		self.__N = 2 ** int(math.ceil(math.log(N, 2)))
		self.__table = [identity_element] * (self.__N * 2 - 1)
		self.__op = operator
		self.__ie = identity_element

	def update(self, idx, x):
		i = self.__N - 1 + idx
		t = self.__table
		o = self.__op
		t[i] = x
		while i != 0:
			pi = (i - 1) // 2
			li = 2 * pi + 1
			ri = 2 * pi + 2
			v = o(t[li], t[ri])
			if t[pi] != v:
				t[pi] = v
			else:
				break
			i = pi

	def query(self, a, b):
		stack = [(0, 0, self.__N)]
		t = self.__table
		o = self.__op
		ans = self.__ie
		c = 0
		while stack:
			c += 1
			(k, l, r) = stack.pop()
			cnd = t[k]
			if a <= l and r <= b:
				ans = o(ans, cnd)
			else:
				if (l + r) // 2 > a and b > l:
					stack.append((2 * k + 1, l, (l + r) // 2))
				if r > a and b > (l + r) // 2:
					stack.append((2 * k + 2, (l + r) // 2, r))
		return ans

	def print(self):
		print(self.__table)

@mt
def slv(N, M, K, A, XY):
	g = defaultdict(set)
	for (x, y) in XY:
		g[x].add(y)
		g[y].add(x)

	def bfs(s):
		q = deque([s])
		done = {s: 0}
		while q:
			u = q.popleft()
			for v in g[u]:
				if v not in done:
					done[v] = done[u] + 1
					q.append(v)
		return done
	from_s = bfs(1)
	from_g = bfs(N)
	C = [(from_s[i] - from_g[i], i) for i in A]
	C.sort()
	ans = 0
	m = -INF
	for (_, a) in C:
		ans = max(ans, m + from_g[a])
		m = max(m, from_s[a])
	return min(from_s[N], ans + 1)

def main():
	(N, M, K) = read_int_n()
	A = read_int_n()
	XY = [read_int_n() for _ in range(M)]
	print(slv(N, M, K, A, XY))
main()


from math import *
from collections import deque
INF = 1 << 60

def main():
	(n, m, k) = map(int, input().split(' '))
	spec = set(map(int, input().split(' ')))
	adjl = [[] for _ in range(0, n + 1)]
	for i in range(0, m):
		(u, v) = map(int, input().split(' '))
		adjl[u].append(v)
		adjl[v].append(u)
	srcdst = bfs(n, adjl, 1)
	enddst = bfs(n, adjl, n)
	diff = [[srcdst[i] - enddst[i], i] for i in range(1, n + 1) if i in spec]
	diff.sort(key=lambda x: x[0])
	mxsrc = -INF
	res = 0
	for x in range(0, len(diff)):
		res = max(res, mxsrc + enddst[diff[x][1]] + 1)
		mxsrc = max(mxsrc, srcdst[diff[x][1]])
	print(min(srcdst[n], res))

def bfs(n, adjl, src):
	q = deque()
	q.append(src)
	odist = [INF for _ in range(0, n + 1)]
	vis = [False for _ in range(0, n + 1)]
	odist[src] = 0
	vis[src] = True
	while len(q) > 0:
		cur = q.popleft()
		for adj in adjl[cur]:
			if not vis[adj]:
				vis[adj] = True
				odist[adj] = odist[cur] + 1
				q.append(adj)
	return odist
main()


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List

def bfs(s, t, edges, dist):
	dist[t] = 0
	step = 0
	q = [t]
	while q:
		step += 1
		nq = []
		for u in q:
			for v in edges[u]:
				if step < dist[v]:
					dist[v] = step
					nq.append(v)
		q = nq

def solve(N, M, K, A, edges):
	dista = [N + 1 for _ in range(N + 1)]
	distb = [N + 1 for _ in range(N + 1)]
	bfs(1, N, edges, dista)
	bfs(N, 1, edges, distb)
	xyd = [(dista[i] - distb[i], i) for i in range(1, N + 1) if A[i]]
	xyd.sort()
	maxx = float('-inf')
	best = 0
	for (d, i) in xyd:
		best = max(best, distb[i] + maxx)
		maxx = max(maxx, dista[i])
	return min(dista[1], best + 1)
(N, M, K) = map(int, input().split())
specials = [int(x) for x in input().split()]
A = [False for _ in range(N + 1)]
for v in specials:
	A[v] = True
edges = [[] for _ in range(N + 1)]
for i in range(M):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	edges[v].append(u)
print(solve(N, M, K, A, edges))


from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush
import os
import sys
from io import BytesIO, IOBase
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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 1000000007
INF = float('inf')

def main():
	(n, m, k) = RL()
	spa = list(RL())
	dic = defaultdict(set)
	ds = 0
	for _ in range(m):
		(a, b) = RL()
		dic[a].add(b)
		dic[b].add(a)

	def bfs(root):
		rec = [0] * (n + 1)
		q = [(root, 0)]
		da = [0] * (n + 1)
		rec[root] = 1
		for (i, d) in q:
			for nex in dic[i]:
				if rec[nex] == 0:
					q.append((nex, d + 1))
					rec[nex] = 1
					da[nex] = d + 1
		return da
	star = bfs(1)
	end = bfs(n)
	res = end[1]
	spa.sort(key=lambda i: star[i] - end[i])
	ts = float('-inf')
	disa = star[spa[0]]
	dis = 0
	for i in spa[1:]:
		dis = max(end[i] + 1 + disa, dis)
		disa = max(disa, star[i])
	print(min(res, dis))
main()


import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, deque

class Node:

	def __init__(self, num, val_1, val_n):
		self.val_1 = val_1
		self.num = num
		self.val_n = val_n

	def __str__(self):
		return f'{self.val_1} {self.val_n} {self.num}'

def bfs(node, val, path):
	curr = deque([node])
	visi = {node}
	(x, tar, inc, new_tar) = (0, 1, 0, 0)
	while len(curr):
		y = curr.popleft()
		val[y] = x
		inc += 1
		for i in path[y]:
			if i not in visi:
				curr.append(i)
				visi.add(i)
				new_tar += 1
		if inc == tar:
			(tar, inc, new_tar) = (new_tar, 0, 0)
			x += 1
	return val

def main():
	(n, m, k) = map(int, input().split())
	spec = list(map(int, input().split()))
	path = defaultdict(list)
	for _ in range(m):
		(x_, y_) = map(int, input().split())
		path[x_].append(y_)
		path[y_].append(x_)
	Val_1 = bfs(1, [0] * (n + 1), path)
	Val_n = bfs(n, [0] * (n + 1), path)
	special = sorted([Node(i, Val_1[i], Val_n[i]) for i in spec], key=lambda x: x.val_1 - x.val_n)
	suf_max = [special[-1].val_n]
	for i in range(len(special) - 2, 0, -1):
		suf_max.append(max(suf_max[-1], special[i].val_n))
	suf_max.reverse()
	ans = 0
	for i in range(len(special) - 1):
		ans = max(ans, min(Val_1[n], special[i].val_1 + suf_max[i] + 1))
	print(ans)
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')
main()


import sys
from collections import deque
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for _ in range(m):
	(v, to) = map(int, input().split())
	g[v].append(to)
	g[to].append(v)
dist_1 = [float('inf')] * (n + 1)
s = 1
dist_1[s] = 0
queue = deque([s])
while queue:
	v = queue.pop()
	for to in g[v]:
		if dist_1[to] > dist_1[v] + 1:
			dist_1[to] = dist_1[v] + 1
			queue.appendleft(to)
dist_n = [float('inf')] * (n + 1)
s = n
dist_n[s] = 0
queue = deque([s])
while queue:
	v = queue.pop()
	for to in g[v]:
		if dist_n[to] > dist_n[v] + 1:
			dist_n[to] = dist_n[v] + 1
			queue.appendleft(to)
a.sort(key=dist_1.__getitem__)

class SegmTree:

	def __init__(self, size):
		N = 1
		while N < size:
			N <<= 1
		self.N = N
		self.tree = [-float('inf')] * (2 * self.N)

	def modify(self, i, value):
		i += self.N
		self.tree[i] = value
		while i > 1:
			self.tree[i >> 1] = max(self.tree[i], self.tree[i ^ 1])
			i >>= 1

	def query_range(self, l, r):
		l += self.N
		r += self.N
		result = -float('inf')
		while l < r:
			if l & 1:
				result = max(result, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				result = max(result, self.tree[r])
			l >>= 1
			r >>= 1
		return result
st = SegmTree(n + 1)
for v in a:
	st.modify(v, dist_n[v])
longestPossible = 0
for v in a:
	st.modify(v, -float('inf'))
	dist = dist_1[v] + 1 + st.query_range(0, n + 1)
	longestPossible = max(longestPossible, dist)
shortDist = min(dist_1[n], longestPossible)
print(shortDist)


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def bfs(p, c, n, tree):
	d = [0] * (n + 1)
	v = [0] * (n + 1)
	q = deque()
	q.append((p, c))
	v[c] = 1
	while q:
		(p, c) = q.pop()
		for i in tree[c]:
			if not v[i]:
				v[i] = 1
				q.appendleft((c, i))
				d[i] = d[c] + 1
	return d

def main():
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	tree = [[] for _ in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		tree[x].append(y)
		tree[y].append(x)
	b = bfs(0, 1, n, tree)
	c = bfs(0, n, n, tree)
	d = []
	for (i, v) in enumerate(a):
		d.append((b[v] - c[v], i))
	d.sort(key=lambda x: x[0])
	f = []
	for i in range(1, k):
		f.append((abs(d[i][0] - d[i - 1][0]), d[i][1], d[i - 1][1]))
	mi = min(f, key=lambda x: x[0])
	print(min(b[n], min(b[a[mi[1]]] + c[a[mi[2]]] + 1, b[a[mi[2]]] + c[a[mi[1]]] + 1)))
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')
main()


import sys
input = sys.stdin.readline
(N, M, K) = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
graph = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)

def bfs(s):
	D = [-1] * N
	D[s] = 0
	q = [s]
	while q:
		qq = []
		for p in q:
			for np in graph[p]:
				if D[np] == -1:
					D[np] = D[p] + 1
					qq.append(np)
		q = qq
	return D
D1 = bfs(0)
D2 = bfs(N - 1)
distance = D1[N - 1]
P = []
for a in A:
	d1 = D1[a]
	d2 = D2[a]
	P.append((d1, d2))
P.sort()
ans = 0
for i in range(K - 1):
	(b1, b2) = P[i]
	(c1, c2) = P[i + 1]
	ans = max(ans, min(c1 + b2 + 1, c2 + b1 + 1))
ans = min(ans, distance)
print(ans)


from collections import deque
import sys
(n, m, k) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
g = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, sys.stdin.readline().split())
	g[x].append(y)
	g[y].append(x)

def bfs(start):
	hold = [0] * (n + 1)
	visited = [False] * (n + 1)
	q = deque()
	q.append(start)
	h = 0
	while len(q) > 0:
		for _ in range(len(q)):
			node = q.popleft()
			visited[node] = True
			hold[node] = h
			for child in g[node]:
				if not visited[child]:
					visited[child] = True
					q.append(child)
		h += 1
	return hold
x = bfs(1)
y = bfs(n)
arr = sorted([(x[i] - y[i], i) for i in a])
(pref, ans) = (-1000000000.0, -1000000000.0)
for (v, node) in arr:
	ans = max(ans, pref + y[node])
	pref = max(pref, x[node])
print(min(x[n], ans + 1))


import sys
from collections import deque
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a = [a[i] - 1 for i in range(k)]
edge = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	edge[x - 1].append(y - 1)
	edge[y - 1].append(x - 1)

def bfs(s):
	dist = [10 ** 20] * n
	que = deque([s])
	dist[s] = 0
	while que:
		v = que.popleft()
		for nv in edge[v]:
			if dist[nv] > dist[v] + 1:
				dist[nv] = dist[v] + 1
				que.append(nv)
	return dist
data1 = bfs(0)
data2 = bfs(n - 1)
s = []
e = []
for i in range(k):
	s.append(data1[a[i]])
	e.append(data2[a[i]])
S = []
E = []
for i in range(k):
	S.append((e[i] - s[i], i, s[i]))
	E.append((e[i] - s[i], i, e[i]))
S.sort()
E.sort()
EE = [E[i][2] for i in range(k)]
for i in range(1, k):
	EE[i] = max(EE[i], EE[i - 1])
ans = 0
for i in range(1, k):
	test = S[i][2] + EE[i - 1] + 1
	ans = max(ans, test)
print(min(data1[-1], ans))


from collections import deque
import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
A = list(map(int, input().split()))
E = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	E[x - 1].append(y - 1)
	E[y - 1].append(x - 1)
d = [[-1, -1] for _ in range(n)]
d[0][0] = 0
todo = deque([0])
while todo:
	v = todo.popleft()
	for u in E[v]:
		if d[u][0] == -1:
			todo.append(u)
			d[u][0] = d[v][0] + 1
d[n - 1][1] = 0
todo = deque([n - 1])
while todo:
	v = todo.popleft()
	for u in E[v]:
		if d[u][1] == -1:
			todo.append(u)
			d[u][1] = d[v][1] + 1
ans = d[n - 1][0]
d_ = []
for a in A:
	d_.append(d[a - 1])
d_.sort()
d_g = [0] * k
d_g[k - 1] = d_[k - 1][1]
for i in range(k - 1, 0, -1):
	d_g[i - 1] = max(d_g[i], d_[i - 1][1])
ans_ = 0
for i in range(k - 1):
	ans_ = max(ans_, d_[i][0] + d_g[i + 1] + 1)
print(min(ans, ans_))


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
al = list(map(int, input().split()))
from collections import defaultdict
g = defaultdict(list)
for _ in range(m):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
	g[y - 1].append(x - 1)
from collections import deque
dist = [-1] * n
que = deque([0])
dist[0] = 0
while que:
	v = que.popleft()
	d = dist[v]
	for w in g[v]:
		if dist[w] > -1:
			continue
		dist[w] = d + 1
		que.append(w)
dist2 = [-1] * n
que = deque([n - 1])
dist2[n - 1] = 0
while que:
	v = que.popleft()
	d = dist2[v]
	for w in g[v]:
		if dist2[w] > -1:
			continue
		dist2[w] = d + 1
		que.append(w)
sorted_al = sorted([(dist[a - 1], a - 1) for a in al])
dist2_al = [dist2[a] for (d, a) in sorted_al]
min_a = float('inf')
ansl = []
for a in dist2_al[::-1]:
	min_a = max(min_a, a)
	ansl.append(a)
ansl = ansl[::-1]
ans = 0
for i in range(k - 1):
	c1 = sorted_al[i][0]
	c2 = ansl[i + 1]
	ans = max(ans, min(c1 + c2 + 1, dist[n - 1]))
print(ans)


import sys
input = sys.stdin.readline
import collections
from collections import defaultdict

def bfs(graph, root):
	visited = set()
	dist = [0] * (n + 1)
	queue = collections.deque([root])
	visited.add(root)
	while queue:
		vertex = queue.popleft()
		for neighbour in graph[vertex]:
			if neighbour not in visited:
				dist[neighbour] = dist[vertex] + 1
				visited.add(neighbour)
				queue.append(neighbour)
	return dist
(n, m, k) = map(int, input().split())
special = [int(i) for i in input().split()]
l1 = [0] * (n + 1)
for j in special:
	l1[j] += 1
graph = defaultdict(list)
ok = False
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x].append(y)
	graph[y].append(x)
putta = bfs(graph, 1)
kl = bfs(graph, n)
new = []
for ljk in range(len(kl)):
	if (putta[ljk] != 0 or kl[ljk] != 0) and l1[ljk] == 1:
		new.append([putta[ljk], kl[ljk]])
new.sort()
for i in range(len(new) - 1):
	if new[i + 1][0] >= new[i][0] and new[i + 1][1] >= new[i][1]:
		ok = True
		break
if ok == True:
	print(putta[n])
else:
	max_ = 0
	for j in range(len(new) - 1):
		max_ = max(max_, new[j][0] + 1 + new[j + 1][1])
	print(min(putta[n], max_))


from sys import stdin, exit
from collections import deque
import operator

def bfs(node):
	d = [-1] * (N + 1)
	d[node] = 0
	q = deque()
	q.append(node)
	while len(q) > 0:
		current = q.pop()
		for i in vertex[current]:
			if d[i] == -1:
				d[i] = d[current] + 1
				q.appendleft(i)
	return d
(N, M, K) = map(int, stdin.readline().split())
special = [int(x) for x in stdin.readline().split()]
vertex = [[] for _ in range(N + 1)]
for i in range(M):
	(x, y) = map(int, stdin.readline().split())
	vertex[x].append(y)
	vertex[y].append(x)
d_1 = bfs(1)
d_N = bfs(N)
short_dist = d_1[N]
dist_pairs = []
for node in special:
	dist_pairs.append((d_1[node], d_N[node]))
dist_pairs.sort(key=operator.itemgetter(0))
for i in range(K - 1):
	(x_1, y_1) = dist_pairs[i]
	(x_2, y_2) = dist_pairs[i + 1]
	if y_1 <= y_2:
		print(short_dist)
		exit()
maxx = 0
for i in range(K - 1):
	(x_1, y_1) = dist_pairs[i]
	(x_2, y_2) = dist_pairs[i + 1]
	if x_1 + y_2 + 1 <= short_dist:
		if x_1 + y_2 + 1 > maxx:
			maxx = x_1 + y_2 + 1
print(maxx)


def bfs(V):
	q = deque()
	q.append(V)
	distance = [-1] * n
	distance[V] = 0
	while len(q) > 0:
		v = q.popleft()
		for u in g[v]:
			if distance[u] != -1:
				continue
			distance[u] = distance[v] + 1
			q.append(u)
	return distance
from collections import deque
import sys
(n, m, k) = map(int, input().split())
a = list(map(lambda x: x - 1, map(int, input().split())))
input = sys.stdin.readlines()
g = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input[i].split())
	x -= 1
	y -= 1
	g[x].append(y)
	g[y].append(x)
dstart = bfs(0)
dend = bfs(n - 1)
p = sorted([(dstart[i], dend[i]) for i in a])
maxs = p[0][0]
answer = 0
for i in range(1, k):
	answer = max(maxs + p[i][1] + 1, answer)
	maxs = max(maxs, p[i][0])
print(min(answer, dend[0]))


from collections import deque
import sys
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
e = [[] for _ in range(n + 1)]
dis = [[-1, -1] for _ in range(n + 1)]

def sol(s, cid):
	dq = deque()
	dq.append(s)
	dis[s][cid] = 0
	while len(dq) > 0:
		now = dq.popleft()
		for u in e[now]:
			if dis[u][cid] == -1:
				dis[u][cid] = dis[now][cid] + 1
				dq.append(u)
lines = sys.stdin.readlines()
for line in lines:
	(x, y) = map(int, line.split())
	e[x].append(y)
	e[y].append(x)
sol(1, 0)
sol(n, 1)
min_dis = dis[n][0]
dis = [dis[x] for x in a]
dis.sort(key=lambda x: x[0] - x[1])
(b_max, ans) = (int(-1000000000.0), 0)
for x in dis[::-1]:
	ans = max(ans, x[0] + b_max)
	b_max = max(b_max, x[1])
print(min(ans + 1, min_dis))


import sys
input = sys.stdin.readline
from collections import deque

def bfs(start):
	dist = [0] * n
	Q = deque()
	visit = [False] * n
	Q.append(start)
	visit[start] = True
	while Q:
		u = Q.popleft()
		for v in adj[u]:
			if not visit[v]:
				dist[v] = dist[u] + 1
				Q.append(v)
				visit[v] = True
	return dist

def lower(a: list, k):
	(l, r) = (0, len(a) - 1)
	ret = -1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] < k:
			ret = mid
			l = mid + 1
		else:
			r = mid - 1
	return ret

def higher(a: list, k):
	(l, r) = (0, len(a) - 1)
	ret = -1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] > k:
			ret = mid
			r = mid - 1
		else:
			l = mid + 1
	return ret
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
	a[i] -= 1
adj = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
left = bfs(0)
right = bfs(n - 1)
ans = left[n - 1]
ld = sorted([left[s] for s in a])
rd = sorted([right[s] for s in a])
for i in range(1, len(ld)):
	if ld[i] == ld[i - 1] or rd[i] == rd[i - 1]:
		print(ans)
		exit()
dd = sorted([(left[s], right[s]) for s in a])
for i in range(1, len(dd)):
	if dd[i][1] > dd[i - 1][1]:
		print(ans)
		exit()
mx = -1
for s in a:
	(l, r) = (left[s], right[s])
	i = lower(ld, l)
	if i != -1:
		cur = ld[i] + 1 + r
		mx = max(mx, cur)
	i = lower(rd, r)
	if i != -1:
		cur = rd[i] + 1 + l
		mx = max(mx, cur)
if mx != -1:
	ans = min(ans, mx)
print(ans)


def bfs(adj, root):
	q = [(root, 0)]
	dist = [0] * len(adj)
	vis = {root}
	i = 0
	while i < len(q):
		(u, d) = q[i]
		i += 1
		dist[u] = d
		for v in adj[u]:
			if v not in vis:
				vis.add(v)
				q.append((v, d + 1))
	return dist

def sol(n, sfs, edges):
	adj = [[] for _ in range(n + 1)]
	for (u, v) in edges:
		adj[u].append(v)
		adj[v].append(u)
	dista = bfs(adj, 1)
	distb = bfs(adj, n)
	orig = distb[1]
	ans = 0
	sfs.sort(key=lambda sf: dista[sf] - distb[sf])
	maxdista = dista[sfs[0]]
	for fs in sfs[1:]:
		ans = max(ans, maxdista + distb[fs])
		maxdista = max(maxdista, dista[fs])
	return min(orig, ans + 1)
(n, m, _) = map(int, input().split())
sfs = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]
print(sol(n, sfs, edges))


import sys
from collections import deque
input = lambda : sys.stdin.readline().strip()
(n, m, k) = map(int, input().split())
bfs = deque()
bfs.append(0)
kol = list(map(int, input().split()))
v = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	b -= 1
	a -= 1
	v[a].append(b)
	v[b].append(a)
lvl = [-1] * n
lvl[0] = 0
while bfs:
	u = bfs.popleft()
	for i in v[u]:
		if lvl[i] == -1:
			bfs.append(i)
			lvl[i] = lvl[u] + 1
bfs.append(n - 1)
lvl1 = [-1] * n
lvl1[n - 1] = 0
while bfs:
	u = bfs.popleft()
	for i in v[u]:
		if lvl1[i] == -1:
			bfs.append(i)
			lvl1[i] = lvl1[u] + 1
kol.sort(key=lambda x: lvl[x - 1] - lvl1[x - 1])
mins = [0]
for i in range(k):
	mins.append(max(lvl1[kol[-i - 1] - 1], mins[-1]))
mins.reverse()
ans = 0
for i in range(k - 1):
	ans = max(ans, lvl[kol[i] - 1] + mins[i + 1] + 1)
print(min(lvl1[0], ans))


from sys import stdin, stdout
from math import *
from heapq import *
from collections import *
(n, m, k, a) = (0, 0, 0, 0)
edge = []

def bfs(root):
	global n, m, k, a, edge
	d = [-1 for u in range(n + 1)]
	d[root] = 0
	q = [root]
	i = 0
	while i < len(q):
		u = q[i]
		for v in edge[u]:
			if d[v] == -1:
				d[v] = d[u] + 1
				q.append(v)
		i = i + 1
	return d

def main():
	global n, m, k, a, edge
	(n, m, k) = [int(x) for x in stdin.readline().split()]
	a = [int(x) for x in stdin.readline().split()]
	edge = [set() for i in range(n + 1)]
	for i in range(m):
		(x, y) = [int(x) for x in stdin.readline().split()]
		edge[x].add(y)
		edge[y].add(x)
	f1 = bfs(1)
	fn = bfs(n)
	sp1 = []
	res1 = f1[n]
	res2 = -1
	sp2 = []
	for u in a:
		if f1[u] >= 0:
			sp1.append((u, f1[u]))
		if fn[u] >= 0:
			sp2.append((u, fn[u]))
	sp1.sort(key=lambda p: -p[1])
	sp2.sort(key=lambda p: -p[1])
	for ind in range(len(sp1) - 1):
		(v, dv) = sp1[ind]
		(u, du) = sp1[ind + 1]
		if v != u:
			res2 = max(res2, min(fn[v] + 1 + f1[u], fn[u] + f1[v] + 1))
		(v, dv) = sp2[ind]
		(u, du) = sp2[ind + 1]
		if v != u:
			res2 = max(res2, min(fn[v] + 1 + f1[u], fn[u] + f1[v] + 1))
	stdout.write('%d' % min(res1, res2))
	return 0
main()


import sys
from collections import deque
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
special = set(map(lambda x: int(x) - 1, input().split()))
flag = 0
adj = [[] for _ in range(n)]
for (u, v) in (map(int, input().split()) for _ in range(m)):
	if u - 1 in special and v - 1 in special:
		flag = 1
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)

def bfs(start):
	inf = 10 ** 18
	dists = [inf] * n
	dists[start] = 0
	dq = deque([start])
	while dq:
		v = dq.popleft()
		for dest in adj[v]:
			if dists[dest] < inf:
				continue
			dists[dest] = dists[v] + 1
			dq.append(dest)
	return dists
dists_1 = bfs(0)
if flag:
	print(dists_1[n - 1])
	exit()
dists_n = bfs(n - 1)
candidate = []
sp = sorted(((dists_1[i], i) for i in special), reverse=True)
candidate.append((sp[0][1], sp[1][1]))
(min_delta, x, y) = (10 ** 18, 0, 0)
for i in range(k - 1):
	if min_delta > sp[i][0] - sp[i + 1][0]:
		min_delta = sp[i][0] - sp[i + 1][0]
		(x, y) = (sp[i][1], sp[i + 1][1])
candidate.append((x, y))
sp = sorted(((dists_n[i], i) for i in special), reverse=True)
candidate.append((sp[0][1], sp[1][1]))
(min_delta, x, y) = (10 ** 18, 0, 0)
for i in range(k - 1):
	if min_delta > sp[i][0] - sp[i + 1][0]:
		min_delta = sp[i][0] - sp[i + 1][0]
		(x, y) = (sp[i][1], sp[i + 1][1])
ans = 0
for (x, y) in candidate:
	adj[x].append(y)
	adj[y].append(x)
	if ans:
		ans = max(ans, bfs(0)[n - 1])
	else:
		ans = bfs(0)[n - 1]
	adj[x].pop()
	adj[y].pop()
print(ans)


from collections import deque

def bfs(g, source):
	n = len(g)
	d = [-1] * n
	q = deque()
	q.append(source)
	d[source] = 0
	while q:
		u = q.popleft()
		for v in g[u]:
			if d[v] == -1:
				d[v] = d[u] + 1
				q.append(v)
	return d
(n, m, k) = [int(_) for _ in input().split()]
specials = [int(_) - 1 for _ in input().split()]
g = [[] for i in range(n)]
for i in range(m):
	(x, y) = [int(_) - 1 for _ in input().split()]
	g[x].append(y)
	g[y].append(x)
dist_src = bfs(g, source=0)
dist_tar = bfs(g, source=n - 1)
specials = list(zip([dist_src[u] for u in specials], [dist_tar[u] for u in specials]))
specials.sort()
max_suff = [0] * k
max_suff[k - 1] = specials[k - 1][1]
for i in range(k - 2, -1, -1):
	max_suff[i] = max(max_suff[i + 1], specials[i][1])
res = 0
for (i, u) in enumerate(specials):
	if i + 1 < k:
		res = max(res, u[0] + max_suff[i + 1] + 1)
print(min(res, dist_src[n - 1]))


import sys
from collections import deque, defaultdict

def bfs(g, source):
	q = deque()
	dist = {}
	q.append(source)
	dist[source] = 0
	while q:
		node = q.popleft()
		assert node in dist
		d = dist[node]
		for nbr in g[node]:
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
	return dist

def solve(N, M, K, A, edges):
	special = set(A)
	g = [[] for i in range(N + 1)]
	for (u, v) in edges:
		g[u].append(v)
		g[v].append(u)
	dist1 = bfs(g, 1)
	dist2 = bfs(g, N)
	shortestDist = dist1[N]
	assert dist1[N] == dist2[1]
	for (u, v) in edges:
		if u in special and v in special:
			return shortestDist
	best = 0
	special = sorted(special, key=lambda x: dist1[x])
	for (u, v) in zip(special, special[1:]):
		if u != v:
			if dist1[u] + 1 + dist2[v] >= shortestDist and dist1[v] + 1 + dist2[u] >= shortestDist:
				return shortestDist
			d = dist1[u] + 1 + dist2[v]
			if d <= shortestDist:
				best = max(best, d)
			d = dist1[v] + 1 + dist2[u]
			if d <= shortestDist:
				best = max(best, d)
	return best
input = sys.stdin.readline
(N, M, K) = map(int, input().split())
A = [int(x) for x in input().split()]
assert len(A) == K
edges = []
for i in range(M):
	edges.append([int(x) for x in input().split()])
ans = solve(N, M, K, A, edges)
print(ans)


import sys, os, io
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(curr):
	q = deque()
	dist = [-1] * n
	q.append(curr)
	dist[curr] = 0
	while q:
		curr = q.popleft()
		for i in graph[curr]:
			if dist[i] == -1:
				dist[i] = dist[curr] + 1
				q.append(i)
	return dist
(n, m, k) = [int(i) for i in input().split()]
a = [int(i) - 1 for i in input().split()]
graph = [[] for i in range(n)]
for i in range(m):
	(ui, vi) = [int(i) - 1 for i in input().split()]
	graph[ui].append(vi)
	graph[vi].append(ui)
da = bfs(0)
db = bfs(n - 1)
xy = [[da[i], db[i]] for i in a]
xy.sort()
m = xy[0][0]
ans = 0
for i in range(1, k):
	ans = max(ans, xy[i - 1][0] + xy[i][1] + 1)
ans = min(ans, da[-1])
print(ans)


def main():
	(n, m, k) = [int(s) for s in input().strip().split()]
	A = [int(s) for s in input().strip().split()]
	adj = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = [int(s) for s in input().strip().split()]
		adj[u].append(v)
		adj[v].append(u)

	def bfs(u):
		result = [float('inf')] * (n + 1)
		result[u] = 0
		step = 0
		q = [u]
		while q:
			step += 1
			newq = []
			for u in q:
				for v in adj[u]:
					if result[v] == float('inf'):
						result[v] = step
						newq.append(v)
			q = newq
		return result
	X = bfs(1)
	Y = bfs(n)
	A.sort(key=lambda a: X[a] - Y[a])
	(result, maxx) = (float('-inf'), float('-inf'))
	for a in A:
		result = max(result, maxx + Y[a])
		maxx = max(maxx, X[a])
	result = min(X[n], result + 1)
	print(result)
main()


import sys
input = sys.stdin.readline
import heapq
from heapq import heappop, heappush
INF = 10 ** 9

class Dijkstra:

	def __init__(self, adj):
		self.n = len(adj)
		self.adj = adj
		self.dist = [INF] * len(adj)
		self.q = []

	def reset(self):
		self.dist = [INF] * self.n
		self.q = []

	def calc(self, start):
		self.dist[start] = 0
		heapq.heappush(self.q, (0, start))
		while len(self.q) != 0:
			(prov_cost, src) = heapq.heappop(self.q)
			if self.dist[src] < prov_cost:
				continue
			for dest in self.adj[src]:
				if self.dist[dest] > self.dist[src] + 1:
					self.dist[dest] = self.dist[src] + 1
					heapq.heappush(self.q, (self.dist[dest], dest))
		return self.dist
(n, m, k) = map(int, input().split())
special = set([int(item) - 1 for item in input().split()])
edge = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	edge[u].append(v)
	edge[v].append(u)
DIJK = Dijkstra(edge)
forward = DIJK.calc(0)
DIJK.reset()
backward = DIJK.calc(n - 1)
sp = []
for (i, (ff, bb)) in enumerate(zip(forward, backward)):
	if i not in special:
		continue
	sp.append((ff, bb))
sp.sort(reverse=True)
queue = []
current = sp[1][0]
heapq.heappush(queue, -sp[0][1])
heapq.heappush(queue, -sp[1][1])
ans = current + min(sp[0][1], sp[1][1])
for (ff, bb) in sp[2:]:
	current = ff
	heappush(queue, -bb)
	m1 = heappop(queue)
	m2 = heappop(queue)
	ans = max(ans, current - max(m1, m2))
	heappush(queue, m1)
	heappush(queue, m2)
print(min(ans + 1, forward[n - 1]))


from collections import deque

def bfs(graph, source):
	n = len(graph)
	dis = [-1] * n
	que = deque()
	que.append(source)
	dis[source] = 0
	while que:
		u = que.popleft()
		for v in graph[u]:
			if dis[v] == -1:
				dis[v] = dis[u] + 1
				que.append(v)
	return dis
(n, m, k) = [int(_) for _ in input().split()]
a = [int(_) - 1 for _ in input().split()]
a.sort()
g = [[] for i in range(n)]
for i in range(m):
	(u, v) = [int(_) - 1 for _ in input().split()]
	g[u].append(v)
	g[v].append(u)
dis_st = bfs(g, 0)
dis_en = bfs(g, n - 1)
nom = [(0, 0)] * k
for i in range(k):
	nom[i] = (dis_st[a[i]] - dis_en[a[i]], a[i])
nom.sort()
ans = 0
Max = -1000000007
for tmp in nom:
	t = tmp[1]
	ans = max(ans, Max + dis_en[t])
	Max = max(Max, dis_st[t])
res = min(dis_st[n - 1], ans + 1)
print(res)


import sys
import heapq
from collections import deque
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
A = list(map(int, input().split()))
E = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
D1 = [-1] * (n + 1)
D1[1] = 0
USE = [0] * (n + 1)
USE[1] = 1
Q = deque()
Q.append(1)
while Q:
	x = Q.popleft()
	for to in E[x]:
		if USE[to] == 1:
			continue
		USE[to] = 1
		D1[to] = D1[x] + 1
		Q.append(to)
D2 = [-1] * (n + 1)
D2[n] = 0
USE = [0] * (n + 1)
USE[n] = 1
Q = deque()
Q.append(n)
while Q:
	x = Q.popleft()
	for to in E[x]:
		if USE[to] == 1:
			continue
		USE[to] = 1
		D2[to] = D2[x] + 1
		Q.append(to)
G = [-1 << 31] * (n + 2)
for a in A:
	if G[D1[a]] != -1 << 31:
		print(D1[n])
		sys.exit()
	G[D1[a]] = D2[a]
ANS = -1 << 31
MAX = -1 << 31
for i in range(n + 1, -1, -1):
	if G[i] == -1 << 31:
		continue
	ANS = max(ANS, i + MAX)
	MAX = G[i]
if ANS < 0:
	print(D1[n])
else:
	print(min(D1[n], ANS + 1))


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
from heapq import heappop, heappush

def dijkstra(start):
	n = len(G)
	dist = [float('inf')] * n
	visited = set()
	heap = []
	heap.append((0, start))
	while heap and len(visited) != n:
		(d, cur) = heappop(heap)
		if cur in visited:
			continue
		visited.add(cur)
		dist[cur] = d
		for to in G[cur]:
			if to not in visited:
				heappush(heap, (d + 1, to))
	return dist
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
b = set(a)
G = [[] for i in range(n)]
flag = False
for i in range(m):
	(x, y) = map(int, input().split())
	if x in b and y in b:
		flag = True
	G[x - 1].append(y - 1)
	G[y - 1].append(x - 1)
forward = dijkstra(0)
backward = dijkstra(n - 1)
kouho = []
c = set()
d = set()
for ai in a:
	c.add(forward[ai - 1])
	d.add(backward[ai - 1])
	kouho.append((forward[ai - 1], backward[ai - 1]))
ans = forward[n - 1]
if len(c) != k or len(d) != k or flag:
	print(ans)
	exit()
tmp = -1
ans_tmp = []
kouho.sort()
for (x, y) in kouho:
	if tmp != -1:
		tmp2 = min(forward[n - 1], tmp + 1 + y)
		ans_tmp.append(tmp2)
	tmp = x
ans = max(ans_tmp) if ans_tmp else ans
print(ans)


import sys
from collections import deque
input = sys.stdin.readline
(N, M, K) = map(int, input().split())
A = list(map(int, input().split()))
d = [set() for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	d[a].add(b)
	d[b].add(a)
queue = deque([1])
vs = set([1])
dist = [0] * (N + 1)
while queue:
	v = queue.popleft()
	for u in d[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist[u] = dist[v] + 1
queue = deque([N])
vs = set([N])
dist2 = [0] * (N + 1)
while queue:
	v = queue.popleft()
	for u in d[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist2[u] = dist2[v] + 1
minr = dist[N]
ps = list()
for a in A:
	ps.append((dist[a], dist2[a]))
ps.sort(key=lambda x: x[0] - x[1])
mns = [0] * (K + 1)
for i in range(K - 1, -1, -1):
	mns[i] = max(ps[i][1], mns[i + 1])
mx = 0
for i in range(K - 1):
	mx = max(ps[i][0] + mns[i + 1], mx)
print(min(minr, mx + 1))


class SegmentTree:

	def __init__(self, arr, func, initialRes=0):
		self.f = func
		self.N = len(arr)
		self.tree = [0 for _ in range(4 * self.N)]
		self.initialRes = initialRes
		for i in range(self.N):
			self.tree[self.N + i] = arr[i]
		for i in range(self.N - 1, 0, -1):
			self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])

	def updateTreeNode(self, idx, value):
		self.tree[idx + self.N] = value
		idx += self.N
		i = idx
		while i > 1:
			self.tree[i >> 1] = self.f(self.tree[i], self.tree[i ^ 1])
			i >>= 1

	def query(self, l, r):
		r += 1
		res = self.initialRes
		l += self.N
		r += self.N
		while l < r:
			if l & 1:
				res = self.f(res, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res = self.f(res, self.tree[r])
			l >>= 1
			r >>= 1
		return res

def getMaxSegTree(arr):
	return SegmentTree(arr, lambda a, b: max(a, b), initialRes=-float('inf'))

def getMinSegTree(arr):
	return SegmentTree(arr, lambda a, b: min(a, b), initialRes=float('inf'))

def getSumSegTree(arr):
	return SegmentTree(arr, lambda a, b: a + b, initialRes=0)
from collections import deque

def main():
	(n, m, k) = readIntArr()
	a = readIntArr()
	adj = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = readIntArr()
		adj[u].append(v)
		adj[v].append(u)
	distFromN = [inf for _ in range(n + 1)]
	distFromN[n] = 0
	q = deque()
	q.append([n, 0])
	while q:
		(node, d) = q.popleft()
		for nex in adj[node]:
			if distFromN[nex] == inf:
				distFromN[nex] = d + 1
				q.append([nex, d + 1])
	isSpecial = [False for _ in range(n + 1)]
	specFieldsDistFromN = [-inf for _ in range(n + 1)]
	for x in a:
		specFieldsDistFromN[x] = distFromN[x]
		isSpecial[x] = True
	stMax = getMaxSegTree(specFieldsDistFromN)
	afterJoiningMax = 0
	q = deque()
	q.append([1, 0])
	visited = [False for _ in range(n + 1)]
	visited[1] = True
	while q:
		(node, d) = q.popleft()
		if isSpecial[node]:
			stMax.updateTreeNode(node, -inf)
			afterJoiningMax = max(afterJoiningMax, d + 1 + stMax.query(1, n))
		for nex in adj[node]:
			if visited[nex] == False:
				visited[nex] = True
				q.append([nex, d + 1])
	ans = min(distFromN[1], afterJoiningMax)
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
main()


import sys
from collections import deque
ip = lambda : sys.stdin.readline()

def f(src, dist):
	q = deque([[src, 0]])
	isv = [False] * n
	while q:
		rmv = q.popleft()
		(node, l) = (rmv[0], rmv[1])
		if isv[node]:
			continue
		isv[node] = True
		dist[node] = l
		for child in g[node]:
			if not isv[child]:
				q.append([child, l + 1])
(n, m, k) = map(int, ip().split())
a = list(map(int, ip().split()))
g = [list() for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, ip().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
dist = [0 for _ in range(n)]
dist2 = [0 for _ in range(n)]
f(0, dist)
f(n - 1, dist2)
a.sort(key=lambda x: dist[x - 1])
ans = 0
for i in range(len(a) - 1):
	ans = max(ans, min(dist[n - 1], dist[a[i] - 1] + dist2[a[i + 1] - 1] + 1))
print(ans)


import sys
from collections import deque
input = sys.stdin.readline
(N, M, K) = map(int, input().split())
A = list(map(int, input().split()))
d = [set() for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	d[a].add(b)
	d[b].add(a)
queue = deque([1])
vs = set([1])
dist = [0] * (N + 1)
while queue:
	v = queue.popleft()
	for u in d[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist[u] = dist[v] + 1
queue = deque([N])
vs = set([N])
dist2 = [0] * (N + 1)
while queue:
	v = queue.popleft()
	for u in d[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist2[u] = dist2[v] + 1
minr = dist[N]
ps = list()
for a in A:
	ps.append((dist[a], dist2[a]))
ps.sort(key=lambda x: (x[0], x[1]))
ps2 = []
(ba, bb) = (None, None)
for (a, b) in ps:
	while ps2:
		(aa, bb) = ps2[-1]
		if a > aa and bb <= b:
			ps2.pop()
			continue
		break
	ps2.append((a, b))
ps = None
tl = len(ps2)
if tl == 0:
	print(minr)
elif tl == 1:
	print(min(minr, ps2[0][0] + ps2[0][1] + 1))
else:
	mxx = 0
	for i in range(tl - 1):
		mxx = max(mxx, min(ps2[i + 1][0] + ps2[i][1], ps2[i][0] + ps2[i + 1][1]) + 1)
	print(min(minr, mxx))


from collections import deque
from sys import stdin
(n, m, k) = map(int, input().split())
s = list(map(int, input().split()))
node = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, stdin.readline().split())
	node[a].append(b)
	node[b].append(a)
q = deque()
(depth, depth2) = ([-1] * (n + 1), [-1] * (n + 1))
q.append(1)
(depth[1], depth2[n]) = (0, 0)
while len(q) > 0:
	p = q[0]
	q.popleft()
	for i in node[p]:
		if depth[i] == -1:
			depth[i] = depth[p] + 1
			q.append(i)
q.append(n)
while len(q) > 0:
	p = q[0]
	q.popleft()
	for i in node[p]:
		if depth2[i] == -1:
			depth2[i] = depth2[p] + 1
			q.append(i)
(x, y, dp, ans) = ([], [], [0] * (k + 1), 0)
for i in range(k):
	x.append([depth[s[i]] - depth2[s[i]], depth[s[i]], depth2[s[i]]])
x.sort()
for i in range(k - 1, -1, -1):
	if i == k - 1:
		dp[i] = x[i][2]
	dp[i] = max(dp[i + 1], x[i][2])
for i in range(k - 1):
	ans = max(ans, x[i][1] + dp[i + 1])
print(min(ans + 1, depth[n]))


from collections import deque
import functools
import sys

def bfs(src, n, g):
	dist = [0] * (n + 1)
	q = deque([src])
	vis = set([src])
	while q:
		rmv = q.popleft()
		if rmv not in g:
			continue
		for child in g[rmv]:
			if dist[child] == 0 and child not in vis:
				dist[child] = 1 + dist[rmv]
				vis.add(child)
				q.append(child)
	return dist
(n, m, k) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
g = {}
for _ in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	if u not in g:
		g[u] = set()
	if v not in g:
		g[v] = set()
	g[u].add(v)
	g[v].add(u)
path1 = bfs(1, n, g)
path2 = bfs(n, n, g)
ans = 0
a = sorted(a, key=lambda x: path1[x])
for i in range(1, len(a)):
	ans = max(ans, min(path1[a[i - 1]] + path2[a[i]] + 1, path1[n]))
print(ans)


import sys
from collections import deque
from itertools import accumulate
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
special = set(map(lambda x: int(x) - 1, input().split()))
flag = 0
adj = [[] for _ in range(n)]
for (u, v) in (map(int, input().split()) for _ in range(m)):
	if u - 1 in special and v - 1 in special:
		flag = 1
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)

def bfs(start):
	inf = 10 ** 18
	dists = [inf] * n
	dists[start] = 0
	dq = deque([start])
	while dq:
		v = dq.popleft()
		for dest in adj[v]:
			if dists[dest] < inf:
				continue
			dists[dest] = dists[v] + 1
			dq.append(dest)
	return dists
dists_1 = bfs(0)
if flag:
	print(dists_1[n - 1])
	exit()
dists_n = bfs(n - 1)
candidate = []
sp = sorted((i for i in special), key=lambda i: dists_1[i] - dists_n[i])
acc1 = list(accumulate((dists_1[i] for i in sp), max))
acc2 = list(accumulate((dists_n[i] for i in reversed(sp)), max))[::-1]
ans = max((acc1[i] + acc2[i + 1] for i in range(k - 1))) + 1
print(min(dists_1[n - 1], ans))


from sys import stdin, stdout
from collections import deque
(n, m, k) = map(int, stdin.readline().split())
alist = list(map(int, stdin.readline().split()))
cnx = {}
for _ in range(m):
	(x, y) = map(int, stdin.readline().split())
	cnx.setdefault(x, []).append(y)
	cnx.setdefault(y, []).append(x)
next = deque([(1, 0)])
scan = set(alist)
d1 = {}
while scan or n not in d1:
	(v1, d) = next.popleft()
	if v1 in d1:
		continue
	if v1 in scan:
		scan.remove(v1)
	d1[v1] = d
	for v2 in cnx[v1]:
		if v2 not in d1:
			next.append((v2, d + 1))
next = deque([(n, 0)])
scan = set(alist)
d2 = {}
while scan:
	(v1, d) = next.popleft()
	if v1 in d2:
		continue
	if v1 in scan:
		scan.remove(v1)
	d2[v1] = d
	for v2 in cnx[v1]:
		if v2 not in d2:
			next.append((v2, d + 1))
alist.sort(key=lambda x: d1[x] - d2[x], reverse=True)
(ans, hi) = (None, None)
for a in alist:
	if hi == None:
		hi = d2[a]
		continue
	ans = d1[a] + hi if not ans else max(ans, d1[a] + hi)
	hi = max(hi, d2[a])
stdout.write(str(min(d1[n], ans + 1)))


import sys
from collections import deque
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 7

def bfs1(node):
	que = deque()
	que.append(node)
	vis = [False] * (n + 1)
	x[node] = 1
	vis[node] = True
	while len(que) > 0:
		par = que.popleft()
		for i in g[par]:
			if not vis[i]:
				x[i] = x[par] + 1
				que.append(i)
				vis[i] = True

def bfs2(node):
	que = deque()
	que.append(node)
	vis = [False] * (n + 1)
	y[node] = 1
	vis[node] = True
	while len(que) > 0:
		par = que.popleft()
		for i in g[par]:
			if not vis[i]:
				y[i] = y[par] + 1
				que.append(i)
				vis[i] = True
(n, m, k) = Ri()
a = Ri()
s = set(a)
g = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = Ri()
	g[a].append(b)
	g[b].append(a)
x = [INF] * (n + 1)
y = [INF] * (n + 1)
bfs1(1)
bfs2(n)
lis = []
for i in range(1, n + 1):
	if i in s:
		lis.append([x[i] - y[i], i])
lis.sort(key=lambda x: x[0])
suf = [-1] * len(lis)
for i in range(len(lis) - 2, -1, -1):
	suf[i] = max(y[lis[i + 1][1]], suf[i + 1])
maxx = -1
for i in range(len(lis) - 1):
	maxx = max(maxx, x[lis[i][1]] + suf[i])
print(min(maxx + 1 - 1 - 1, x[n] - 1))


import sys
input = sys.stdin.readline
from collections import deque

def bfs(start):
	dist = [0] * n
	Q = deque()
	visit = [False] * n
	Q.append(start)
	visit[start] = True
	while Q:
		u = Q.popleft()
		for v in adj[u]:
			if not visit[v]:
				dist[v] = dist[u] + 1
				Q.append(v)
				visit[v] = True
	return dist
(n, m, k) = map(int, input().split())
a = list(map(lambda x: x - 1, map(int, input().split())))
adj = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
left = bfs(0)
right = bfs(n - 1)
ans = left[n - 1]
b = [(left[s], right[s]) for s in a]
b.sort(key=lambda x: x[0] - x[1])
best = b[k - 1][1]
mx = 0
for i in range(k - 2, -1, -1):
	cur = b[i][0] + 1 + best
	mx = max(mx, cur)
	best = max(best, b[i][1])
ans = min(ans, mx)
print(ans)