In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y, there is a bidirectional road between towns x and y if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.

A train and a bus leave town 1 at the same time. They both have the same destination, town n, and don't make any stops on the way (but they can wait in town n). The train can move only along railways and the bus can move only along roads.

You've been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n) simultaneously.

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town n (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town n at the same moment of time, but are allowed to do so.


-----Input-----

The first line of the input contains two integers n and m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n - 1) / 2) — the number of towns and the number of railways respectively.

Each of the next m lines contains two integers u and v, denoting a railway between towns u and v (1 ≤ u, v ≤ n, u ≠ v).

You may assume that there is at most one railway connecting any two towns.


-----Output-----

Output one integer — the smallest possible time of the later vehicle's arrival in town n. If it's impossible for at least one of the vehicles to reach town n, output  - 1.


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

Output
2

Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output
-1

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

Output
3



-----Note-----

In the first sample, the train can take the route $1 \rightarrow 3 \rightarrow 4$ and the bus can take the route $1 \rightarrow 2 \rightarrow 4$. Note that they can arrive at town 4 at the same time.

In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there's no way for the bus to reach town 4.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
import sys
d = [[0 for col in range(500)] for row in range(500)]
v = [0] * 500
(n, m) = list(map(int, input().split()))
for i in range(m):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	d[x][y] = d[y][x] = 1
q = [0]
l = 0
while l < len(q):
	for i in range(1, n):
		if d[0][n - 1] != d[q[l]][i] and v[i] == 0:
			v[i] = v[q[l]] + 1
			q.append(i)
	l += 1
if v[n - 1] == 0:
	print(-1)
else:
	print(v[n - 1])


def BFS(start):
	queue = [start]
	visited = [False] * n
	visited[start] = True
	dists = [0] * n
	while len(queue):
		current = queue.pop(0)
		for i in graph[current]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True
				dists[i] = dists[current] + 1
	return dists[n - 1]
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
if n - 1 in graph[0]:
	for i in range(n):
		graph[i] = [j for j in range(n) if j not in graph[i] and j != i]
answer = BFS(0)
print(-1 if answer == 0 else answer)


from queue import Queue
(n, m) = map(int, input().split())
roads = [[1 for i in range(n)] for j in range(n)]
dist = [500 for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	roads[x][y] = 2
	roads[y][x] = 2
value = roads[0][n - 1]
dist[0] = 0
aux = Queue()
aux.put(0)
while not aux.empty():
	top = aux.get()
	for i in range(len(roads[0])):
		edge = roads[top][i]
		if edge != value and dist[top] + 1 < dist[i]:
			aux.put(i)
			dist[i] = dist[top] + 1
if dist[n - 1] != 500:
	print(dist[n - 1])
else:
	print('-1')


def routes(n, m):
	distance = [0] * (n + 1)
	for i in range(n + 1):
		distance[i] = [1] * (n + 1)
	for x in range(m):
		(a, b) = map(int, input().split())
		distance[a][b] = distance[b][a] = 2
	x = 3 - distance[1][n]
	y = [0] * (n + 1)
	i = 1
	d = [n + 1] * (n + 1)
	result = d[1] = 0
	while i != n:
		y[i] = 1
		for j in range(1, n + 1):
			if y[j] == 0 and distance[i][j] == x and (d[j] > d[i] + 1):
				d[j] = d[i] + 1
		end = n + 1
		for j in range(1, n + 1):
			if y[j] == 0 and d[j] < end:
				end = d[j]
				i = j
		if end == n + 1:
			result = -1
			break
		elif i == n:
			result = d[n]
			break
	return result
(n, m) = map(int, input().split())
print(routes(n, m))


(towns, no_railways) = map(int, input().split())
railways = {x: [] for x in range(towns)}
roads = {x: [] for x in range(towns)}

def shortest_path(graph, start, goal):
	explored = []
	queue = [[start]]
	if start == goal:
		return
	while queue:
		path = queue.pop(0)
		node = path[-1]
		if node not in explored:
			neighbours = graph[node]
			for neighbour in neighbours:
				new_path = list(path)
				new_path.append(neighbour)
				queue.append(new_path)
				if neighbour == goal:
					return len(new_path) - 1
			explored.append(node)
	return -1
for _ in range(no_railways):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	railways[u].append(v)
	railways[v].append(u)
for u in range(towns):
	for v in range(towns):
		if u != v:
			if v not in railways[u]:
				roads[u].append(v)
if towns - 1 in railways[0]:
	print(shortest_path(roads, 0, towns - 1))
else:
	print(shortest_path(railways, 0, towns - 1))


(n, m) = map(int, input().split())
L = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	L[a].append(b)
	L[b].append(a)
if n not in L[1]:
	l = [1]
	D = [-1 for i in range(n + 1)]
	D[1] = 0
	while len(l) >= 1:
		t = l[0]
		del l[0]
		for x in L[t]:
			if D[x] == -1 or D[x] > D[t] + 1:
				l.append(x)
				D[x] = D[t] + 1
	print(D[n])
else:
	M = [[] for i in range(n + 1)]
	for i in range(1, n + 1):
		L[i].append(0)
		L[i].append(n + 1)
		T = sorted(L[i])
		for j in range(len(T) - 1):
			for v in range(T[j] + 1, T[j + 1]):
				if v != i:
					M[i].append(v)
	l = [1]
	D = [-1 for i in range(n + 1)]
	D[1] = 0
	while len(l) >= 1:
		t = l[0]
		del l[0]
		for x in M[t]:
			if D[x] == -1 or D[x] > D[t] + 1:
				l.append(x)
				D[x] = D[t] + 1
	print(D[n])


from queue import PriorityQueue

class Graph:
	to = []
	n = 0

	def __init__(self, _n):
		self.to = [[False] * (_n + 1) for i in range(_n + 1)]
		self.n = _n

	def add_edge(self, s, t):
		self.to[s][t] = True
		self.to[t][s] = True

	def dijkstra(self):
		flag = self.to[1][self.n] == False
		ans = 1
		dis = [-1] * (self.n + 1)
		q = PriorityQueue()
		q.put((0, 1))
		while q.qsize() > 0:
			(d1, pos) = q.get()
			if dis[pos] != -1:
				continue
			dis[pos] = d1
			for i in range(1, self.n + 1):
				if self.to[pos][i] != flag:
					continue
				nx = i
				if nx == pos:
					continue
				if dis[nx] == -1:
					q.put((d1 + 1, nx))
		return dis[self.n]
gph = Graph(0)
(N, M) = [0] * 2

def read_in():
	global N, M, gph
	(N, M) = [int(i) for i in input().split()]
	gph = Graph(N)
	for i in range(M):
		(s, t) = [int(i) for i in input().split()]
		gph.add_edge(s, t)
read_in()
print(gph.dijkstra())


from collections import defaultdict

def find_path_length(g, start, end):
	q = [start]
	weight = 0
	while q:
		weight += 1
		nq = []
		for next in q:
			for e in list(g[next]):
				if e == end:
					return weight
				g[next].discard(e)
				g[e].discard(next)
				nq.append(e)
		q = nq
	return -1

def solve(n, m, railways):
	g_train = defaultdict(set)
	g_bus = defaultdict(set)
	for (a, b) in railways:
		g_train[b].add(a)
		g_train[a].add(b)
	for i in range(1, n):
		for j in range(2, n + 1):
			if j not in g_train[i]:
				g_bus[i].add(j)
				g_bus[j].add(i)
	if len(g_train[n]) == n - 1 or len(g_train[n]) == 0:
		return -1
	if n in g_train[1]:
		return find_path_length(g_bus, 1, n)
	else:
		return find_path_length(g_train, 1, n)
(n, m) = map(int, input().split())
railways = []
for _ in range(m):
	(a, b) = map(int, input().split())
	railways.append((a, b))
print(solve(n, m, railways))


(n, m) = map(int, input().split())
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
level = [-1 for i in range(n + 1)]
stack = []

def bfs(src, lvl, flag):
	level[src] = lvl
	stack.append(src)
	p = 0
	while True:
		for i in range(1, n + 1):
			if dp[src][i] == flag:
				if level[i] == -1:
					stack.append(i)
					level[i] = level[src] + 1
		if len(stack) <= p + 1:
			break
		p += 1
		src = stack[p]
		if src == n:
			return level[src]
			break
	return -1
for i in range(m):
	(a, b) = map(int, input().split())
	dp[a][b] = 1
	dp[b][a] = 1
if dp[1][n]:
	print(bfs(1, 0, 0))
else:
	print(bfs(1, 0, 1))


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))

def dijakstra(weight, k):
	heap = [(0, k)]
	heapify(heap)
	dist = defaultdict(tuple)
	while heap:
		(cost, u) = heappop(heap)
		if u not in dist:
			dist[u] = cost
			for v in weight[u]:
				heappush(heap, (dist[u] + weight[u][v], v))
	return dist
(n, m) = Neo()
(G1, G2) = (defaultdict(dict), defaultdict(dict))
s = set()
for i in range(m):
	(u, v) = Neo()
	G1[u][v] = 1
	G1[v][u] = 1
	s.add((u, v))
	s.add((v, u))
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if (i, j) not in s:
			G2[i][j] = 1
			G2[j][i] = 1
if (1, n) in s:
	dist = dijakstra(G2, 1)
	if n not in dist:
		print(-1)
	else:
		print(dist[n])
else:
	dist = dijakstra(G1, 1)
	if n not in dist:
		print(-1)
	else:
		print(dist[n])


(n, m) = map(int, input().split())
dist = [[1 for col in range(n + 1)] for row in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	dist[a][b] = 2
	dist[b][a] = 2
x = 3 - dist[1][n]
(res, i) = (0, 1)
vis = [0] * (n + 1)
d = [n + 1] * (n + 1)
d[1] = 0
while i != n:
	vis[i] = 1
	for j in range(1, n + 1):
		if vis[j] == 0 and dist[i][j] == x and (d[j] > d[i] + 1):
			d[j] = d[i] + 1
	mine = n + 1
	for j in range(1, n + 1):
		if vis[j] == 0 and d[j] < mine:
			mine = d[j]
			i = j
	if mine == n + 1:
		res = -1
		break
	if i == n:
		res = d[n]
		break
print(res)


from collections import deque
(n, m) = map(int, input().split())
g_trn = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g_trn[u - 1].append(v - 1)
	g_trn[v - 1].append(u - 1)
g_bus = [list(set(range(n)) - set(g_trn[i])) for i in range(n)]
queue_bus = deque()
queue_bus.appendleft(0)
dist_bus = [-1 for _ in range(n)]
dist_bus[0] = 0
while queue_bus:
	node = queue_bus.pop()
	for neigh in g_bus[node]:
		if dist_bus[neigh] == -1:
			dist_bus[neigh] = dist_bus[node] + 1
			queue_bus.appendleft(neigh)
if dist_bus[-1] == -1:
	print(-1)
	exit()
queue_trn = deque()
queue_trn.appendleft(0)
dist_trn = [-1 for _ in range(n)]
dist_trn[0] = 0
while queue_trn:
	node = queue_trn.pop()
	for neigh in g_trn[node]:
		new_dist = dist_trn[node] + 1
		if dist_trn[neigh] == -1:
			dist_trn[neigh] = new_dist
			queue_trn.appendleft(neigh)
if dist_trn[-1] == -1:
	print(-1)
	exit()

def solve_onedir(g, dist_1, dist_orig):
	queue_2 = deque()
	queue_2.appendleft(0)
	dist_2 = [-1 for _ in range(n)]
	dist_2[0] = 0
	while queue_2:
		node = queue_2.pop()
		for neigh in g[node]:
			new_dist = dist_2[node] + 1
			if dist_2[neigh] == -1 and new_dist != dist_1[neigh]:
				dist_2[neigh] = new_dist
				queue_2.appendleft(neigh)
	if dist_2[-1] == -1:
		dist_2[-1] = dist_orig[-1] + 2
	return max(dist_1[-1], dist_2[-1])
ans = min(solve_onedir(g_trn, dist_bus, dist_trn), solve_onedir(g_bus, dist_trn, dist_bus))
print(ans)


(n, m) = map(int, input().split())
g = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	g[x][y] = g[y][x] = 1
vis = [-1] * (n + 1)
vis[1] = 0
q = [1]
while q:
	i = q.pop(0)
	for j in range(1, n + 1):
		if g[i][j] != g[1][n] and vis[j] == -1:
			vis[j] = vis[i] + 1
			q.append(j)
print(vis[-1])


f = lambda : map(int, input().split())
(n, m) = f()
w = [[] for i in range(n)]
w1 = [[] for i in range(n)]
l = False
for i in range(m):
	(a, b) = f()
	w[a - 1].append(b - 1)
	w[b - 1].append(a - 1)
	if a == 1 and b == n or (a == n and b == 1):
		l = True
if l:
	for i in range(n):
		for j in range(n):
			if j != i and j not in w[i]:
				w1[i].append(j)
INF = 10 ** 9
dist = [INF] * n
dist[0] = 0
used = [False] * n
min_dist = 0
min_vertex = 0
if not l:
	while min_dist < INF:
		i = min_vertex
		used[i] = True
		for j in w[i]:
			if dist[i] + 1 < dist[j]:
				dist[j] = dist[i] + 1
		min_dist = INF
		for i in range(n):
			if not used[i] and dist[i] < min_dist:
				min_dist = dist[i]
				min_vertex = i
else:
	while min_dist < INF:
		i = min_vertex
		used[i] = True
		for j in w1[i]:
			if dist[i] + 1 < dist[j]:
				dist[j] = dist[i] + 1
		min_dist = INF
		for i in range(n):
			if not used[i] and dist[i] < min_dist:
				min_dist = dist[i]
				min_vertex = i
print(dist[-1] if dist[-1] != INF else -1)


import math
from queue import Queue
(n_cities, n_railways) = map(int, input().split())
roads = [None] * n_cities
arr = [None] * n_cities
for i in range(n_cities):
	queue = [None] * n_cities
	for j in range(n_cities):
		queue[j] = 1
	roads[i] = queue
	arr[i] = math.inf
for i in range(n_railways):
	(city_u, city_v) = map(int, input().split())
	city_u -= 1
	city_v -= 1
	roads[city_u][city_v] = 2
	roads[city_v][city_u] = 2
queue = Queue()
queue.put(0)
arr[0] = 0
while not queue.empty():
	top = queue.get()
	value = roads[0][n_cities - 1]
	for i in range(len(roads[0])):
		vertice = roads[top][i]
		if vertice != value and arr[top] + 1 < arr[i]:
			queue.put(i)
			arr[i] = arr[top] + 1
time_min = arr[n_cities - 1]
if arr[n_cities - 1] != math.inf:
	print(time_min)
else:
	print('-1')


(n, m) = map(int, input().split())
x = [0] * n
for i in range(n):
	x[i] = [0] * n
for i in range(m):
	(a, b) = map(int, input().split())
	x[a - 1][b - 1] = 1
	x[b - 1][a - 1] = 1
visited = set()
visited |= set([0])
stack = []
stack.append((0, 0))
while stack != []:
	cur = stack.pop(0)
	t = 0
	for i in range(n):
		if i not in visited:
			if x[cur[0]][i] == 1:
				stack.append((i, cur[1] + 1))
				visited |= set([i])
				t += 1
	if n - 1 in visited:
		break
first = -1
for i in range(len(stack)):
	if stack[i][0] == n - 1:
		first = stack[i][1]
visited = set()
visited |= set([0])
stack = []
stack.append((0, 0))
while stack != []:
	cur = stack.pop(0)
	t = 0
	for i in range(n):
		if i not in visited:
			if x[cur[0]][i] == 0:
				stack.append((i, cur[1] + 1))
				visited |= set([i])
				t += 1
	if n - 1 in visited:
		break
second = -1
for i in range(len(stack)):
	if stack[i][0] == n - 1:
		second = stack[i][1]
if first == -1 or second == -1:
	print('-1')
else:
	print(max(first, second))


(n, m) = map(int, input().split())
(g1, g2) = ({}, {})
e = [[False for i in range(n)] for j in range(n)]
level = [-1] * n

def bfs(t, u):
	queue = [u]
	level[u] = 0
	while len(queue) != 0:
		u = queue.pop(0)
		if u == n - 1:
			return level[u]
		if t == 1:
			for v in g1[u]:
				if level[v] == -1:
					level[v] = level[u] + 1
					queue.append(v)
		elif t == 2:
			for v in g2[u]:
				if level[v] == -1:
					level[v] = level[u] + 1
					queue.append(v)
	return -1
for i in range(n):
	g1[i] = []
	g2[i] = []
while m:
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g1[a].append(b)
	g1[b].append(a)
	e[a][b] = True
	e[b][a] = True
	m -= 1
for i in range(n):
	for j in range(i + 1, n):
		if not e[i][j]:
			g2[i].append(j)
			g2[j].append(i)
if e[0][n - 1]:
	print(bfs(2, 0))
else:
	print(bfs(1, 0))


from collections import deque as dq
import heapq as hq

class Graph:

	def __init__(self, n=0):
		self.nv = n
		self.g = [[] for i in range(n)]

	def readUdUwGraph(self, m):
		global visite
		for i in range(m):
			(a, b) = map(int, input().split())
			self.g[a - 1].append(b - 1)
			self.g[b - 1].append(a - 1)
			visite.add((min((a - 1, b - 1)), max((a - 1, b - 1))))

	def bfs(self, u):
		global n
		t = [-1] * n
		L = dq()
		L.append(u)
		t[u] = 0
		while len(L) != 0:
			v = L.popleft()
			if v == n - 1:
				return t[v]
			for x in self.g[v]:
				if t[x] == -1:
					L.append(x)
					t[x] = t[v] + 1
		return -1
(n, m) = map(int, input().split())
visite = set()
g = Graph(n)
g1 = Graph(n)
g.readUdUwGraph(m)
for i in range(n):
	for j in range(i + 1, n):
		if (i, j) not in visite:
			g1.g[i].append(j)
			g1.g[j].append(i)
x1 = g.bfs(0)
x2 = g1.bfs(0)
if x1 == -1 or x2 == -1:
	print(-1)
else:
	print(max(x1, x2))


(n, m) = map(int, input().split())
a = [[0] * n for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	a[x - 1][y - 1] = a[y - 1][x - 1] = 1
b = [-1] * n
b[0] = 0
q = [0]
while q:
	u = q.pop(0)
	for v in range(n):
		if a[u][v] != a[0][n - 1] and b[v] == -1:
			b[v] = b[u] + 1
			q.append(v)
print(b[n - 1])


def bfs(V, start):
	D = [None] * (n + 1)
	D[start] = 0
	Q = [start]
	Qstart = 0
	while Qstart < len(Q):
		u = Q[Qstart]
		Qstart += 1
		for v in V[u]:
			if D[v] is None:
				D[v] = D[u] + 1
				Q.append(v)
	return D[n]
(n, m) = tuple(map(int, input().split()))
l1 = [set() for i in range(n + 1)]
l = [set() for i in range(n + 1)]
for i in range(m):
	edge = list(map(int, input().split()))
	l[edge[0]].add(edge[1])
	l[edge[1]].add(edge[0])
if n not in l[1]:
	print(bfs(l, 1) if bfs(l, 1) != None else -1)
else:
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if j not in l[i]:
				l1[i].add(j)
	print(bfs(l1, 1) if bfs(l1, 1) != None else -1)


R = lambda : map(int, input().split())
(n, m) = R()
rail = [[] for _ in range(n)]
rs = set()
for _ in range(m):
	(u, v) = R()
	rail[u - 1].append(v - 1)
	rail[v - 1].append(u - 1)
	rs.add((u - 1, v - 1))
	rs.add((v - 1, u - 1))
road = [[] for _ in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		if (i, j) not in rs:
			road[i].append(j)
			road[j].append(i)

def bfs(adj, i, j):
	from collections import deque
	(q, seen) = (deque(), set())
	q.append((i, 0))
	while q:
		(v, d) = q.popleft()
		for nv in adj[v]:
			if nv not in seen:
				if nv == j:
					return d + 1
				seen.add(nv)
				q.append((nv, d + 1))
	return -1
res_road = bfs(road, 0, n - 1)
res_rail = bfs(rail, 0, n - 1)
if res_rail < 0 or res_road < 0:
	print(-1)
else:
	print(max(res_rail, res_road))


(n, m) = map(int, input().split())
dist = [0] * (n + 1)
for row in range(n + 1):
	dist[row] = [1] * (n + 1)
for i in range(m):
	(a, b) = map(int, input().split())
	dist[a][b] = dist[b][a] = 2
(x, v, i) = (3 - dist[1][n], [0] * (n + 1), 1)
d = [n + 1] * (n + 1)
res = d[1] = 0
while i != n:
	v[i] = 1
	for j in range(1, n + 1):
		if v[j] == 0 and dist[i][j] == x and (d[j] > d[i] + 1):
			d[j] = d[i] + 1
	meu = n + 1
	for j in range(1, n + 1):
		if v[j] == 0 and d[j] < meu:
			meu = d[j]
			i = j
	if meu == n + 1:
		res = -1
		break
	elif i == n:
		res = d[n]
		break
print(res)


(n, m) = map(int, input().split())
s = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	s[a - 1][b - 1] = 1
	s[b - 1][a - 1] = 1
k = 0
a = [0]
vzyali = [False] * n
vzyali[0] = True
ans1 = 0
prev = [0] * n
while len(a) > k and ans1 == 0:
	for i in range(n):
		if s[a[k]][i] == 1 and (not vzyali[i]):
			a.append(i)
			prev[i] = prev[a[k]] + 1
			vzyali[i] = True
			if i == n - 1:
				ans1 = prev[i]
				break
	k += 1
vzyali = [False] * n
vzyali[0] = True
ans2 = 0
k = 0
a = [0]
prev = [0] * n
while len(a) > k and ans2 == 0:
	for i in range(n):
		if s[a[k]][i] == 0 and (not vzyali[i]):
			a.append(i)
			prev[i] = prev[a[k]] + 1
			vzyali[i] = True
			if i == n - 1:
				ans2 = prev[i]
				break
	k += 1
if ans1 > 0 and ans2 > 0:
	print(max(ans1, ans2))
else:
	print(-1)


f = lambda : list(map(int, input().split()))
(n, m) = f()
k = n + 1
s = [[0] * k for i in range(k)]
for j in range(m):
	(u, v) = f()
	s[u][v] = s[v][u] = 1
d = [-1] * k
d[1] = 0
q = [1]
while q:
	u = q.pop(0)
	for v in range(1, k):
		if s[u][v] != s[1][n] and d[v] == -1:
			d[v] = d[u] + 1
			q.append(v)
print(d[n])


from collections import deque
[n, m] = [int(i) for i in input().split()]
routes = [set() for i in range(n + 1)]
for i in range(m):
	[x, y] = [int(j) for j in input().split()]
	routes[x].add(y)
	routes[y].add(x)
if n not in routes[1]:
	a = True
else:
	a = False
way = deque()
way.append(1)
b = [-1 for i in range(n + 1)]
b[1] = 0
while len(way) > 0:
	c = way.popleft()
	for i in range(1, n + 1):
		if a ^ (i in routes[c]):
			continue
		if b[i] == -1:
			b[i] = b[c] + 1
			way.append(i)
			if i == n:
				print(b[i])
				exit(0)
print(-1)


import heapq
(N, M) = map(int, input().split())
used = {(i, j): False for i in range(1, N + 1) for j in range(1, N + 1)}
graph = {i: [] for i in range(1, N + 1)}
graph_r = {i: [] for i in range(1, N + 1)}
for _ in range(M):
	(u, v) = map(int, input().split())
	graph[u].append((1, v))
	graph[v].append((1, u))
	used[u, v] = True
	used[v, u] = True
for i in range(1, N + 1):
	for j in range(1, N + 1):
		if used[i, j] == False:
			graph_r[i].append((1, j))

def dijkstra(s, graph, n):
	dist = [float('inf') for i in range(n + 1)]
	dist[s] = 0
	pq = []
	heapq.heapify(pq)
	heapq.heappush(pq, (0, s))
	while pq:
		(mini_dis, node) = heapq.heappop(pq)
		if dist[node] < mini_dis:
			continue
		for (w, point) in graph[node]:
			if dist[point] < w:
				continue
			newlen = dist[node] + w
			if newlen < dist[point]:
				heapq.heappush(pq, (newlen, point))
				dist[point] = newlen
	return dist
A = dijkstra(1, graph, N)[N]
B = dijkstra(1, graph_r, N)[N]
ans = max(A, B)
if ans == float('inf'):
	print(-1)
else:
	print(ans)


def bsf(grafo):
	fila = [0]
	visitado = [False] * n
	visitado[0] = True
	dists = [0] * n
	while len(fila):
		current = fila.pop(0)
		for i in grafo[current]:
			if not visitado[i]:
				fila.append(i)
				visitado[i] = True
				dists[i] = dists[current] + 1
	return dists[n - 1] if dists[n - 1] != 0 else -1
(n, m) = map(int, input().split())
grafo = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	grafo[u - 1] += [v - 1]
	grafo[v - 1] += [u - 1]
if n - 1 in grafo[0]:
	for i in range(n):
		grafo[i] = [j for j in range(n) if j not in grafo[i] and j != i]
print(bsf(grafo))


from collections import defaultdict

def bfs(graph, m):
	(v, q) = ([], [(0, 0)])
	while len(q):
		(value, d) = q.pop(0)
		if value in v:
			continue
		v.append(value)
		if value == m:
			return d
		for ad in graph[value]:
			if not ad in v:
				q.append((ad, d + 1))
	return -1
(n, m) = map(int, input().split())
(g1, g2) = (defaultdict(list), defaultdict(list))
for i in range(m):
	(b, b1) = map(int, input().split())
	g1[b - 1].append(b1 - 1)
	g1[b1 - 1].append(b - 1)
for i in range(n):
	for j in range(n):
		if i != j:
			if j not in g1[i]:
				g2[i].append(j)
(d1, d2) = (bfs(g1, n - 1), bfs(g2, n - 1))
result = max(d1, d2) if d2 != -1 and d1 != -1 else -1
print(result)


import math
from queue import Queue
(num_de_cidades, num_de_ferrovias) = map(int, input().split())
estradas = [None] * num_de_cidades
aux = [None] * num_de_cidades
for i in range(num_de_cidades):
	fila = [None] * num_de_cidades
	for j in range(num_de_cidades):
		fila[j] = 1
	estradas[i] = fila
	aux[i] = math.inf
for i in range(num_de_ferrovias):
	(cidade_u, cidade_v) = map(int, input().split())
	cidade_u -= 1
	cidade_v -= 1
	estradas[cidade_u][cidade_v] = 2
	estradas[cidade_v][cidade_u] = 2
fila = Queue()
fila.put(0)
aux[0] = 0
while not fila.empty():
	topo = fila.get()
	valor = estradas[0][num_de_cidades - 1]
	for i in range(len(estradas[0])):
		vertice = estradas[topo][i]
		if vertice != valor and aux[topo] + 1 < aux[i]:
			fila.put(i)
			aux[i] = aux[topo] + 1
tempo_min = aux[num_de_cidades - 1]
if aux[num_de_cidades - 1] != math.inf:
	print(tempo_min)
else:
	print('-1')


(n, m) = map(int, input().split())
l = [[0] * n for i in range(n)]
j = [-1] * n
j[0] = 0
k = [0]
for i in range(m):
	(u, v) = map(int, input().split())
	l[u - 1][v - 1] = l[v - 1][u - 1] = 1
while k:
	u = k.pop(0)
	for i in range(n):
		if l[u][i] != l[0][n - 1] and j[i] == -1:
			j[i] = j[u] + 1
			k.append(i)
print(j[n - 1])


import math
from collections import deque
d = {}

def dfs(g, u, step):
	d[u] = step
	for v in g[u]:
		if v not in d or d[v] > step + 1:
			dfs(g, v, step + 1)

def main():
	(n, m) = map(int, input().split())
	g = []
	gg = []
	for _ in range(n):
		g.append([])
		gg.append([])
	for _ in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		g[u].append(v)
		g[v].append(u)
	for i in range(n):
		for j in range(n):
			if i != j and j not in g[i]:
				gg[i].append(j)
	dfs(g, 0, 0)
	global d
	a1 = -1
	if n - 1 in d:
		a1 = d[n - 1]
	d = {}
	dfs(gg, 0, 0)
	a2 = -1
	if n - 1 in d:
		a2 = d[n - 1]
	if a1 < 0 or a2 < 0:
		print(-1)
	else:
		print(max(a1, a2))
main()


from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
adj = [[0 for j in range(n + 1)] for i in range(n + 1)]
edges = [tuple(map(int, input().split())) for _ in range(m)]
for (u, v) in edges:
	(adj[u][v], adj[v][u]) = (1, 1)

def bfs(i, j):
	marked = [0 for t in range(n + 1)]
	dist = [-1 for t in range(n + 1)]
	que = []
	que.append(i)
	marked[i] = 1
	dist[i] = 0
	while que:
		v = que[0]
		que.pop(0)
		for k in range(1, n + 1):
			if adj[v][k] == 1 and marked[k] == 0:
				que.append(k)
				marked[k] = 1
				dist[k] = dist[v] + 1
	return dist[j]
if adj[1][n] == 0:
	print(bfs(1, n))
	exit()
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if i != j:
			adj[i][j] = 1 - adj[i][j]
print(bfs(1, n))


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

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

def pt(x):
	print(x)

def ip():
	return int(input())

class Stack(object):

	def __init__(self):
		self.items = []

	def push(self, new):
		self.items.append(new)

	def pop(self):
		return self.items.pop(0)

	def empty(self):
		return self.items == []
(n, m) = mp()
Rail = [[] for i in range(n)]
Road = [[i for i in range(n)] for j in range(n)]
for i in range(m):
	(u, v) = mp()
	Rail[u - 1].append(v - 1)
	Rail[v - 1].append(u - 1)
	Road[u - 1].remove(v - 1)
	Road[v - 1].remove(u - 1)
visited = [False] * n
time = [float('inf')] * n
if n - 1 in Road[0]:
	Q = Stack()
	Q.push(0)
	visited[0] = True
	time[0] = 0
	while not Q.empty() and (not visited[n - 1]):
		r = Q.pop()
		for i in Rail[r]:
			if not visited[i]:
				visited[i] = True
				time[i] = time[r] + 1
				Q.push(i)
	if not visited[n - 1]:
		print(-1)
	else:
		print(time[n - 1])
else:
	Q = Stack()
	Q.push(0)
	visited[0] = True
	time[0] = 0
	while not Q.empty() and (not visited[n - 1]):
		r = Q.pop()
		for i in Road[r]:
			if not visited[i]:
				visited[i] = True
				time[i] = time[r] + 1
				Q.push(i)
	if not visited[n - 1]:
		print(-1)
	else:
		print(time[n - 1])


(n, m) = map(int, input().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u][v] = graph[v][u] = 1
vis = [-1] * (n + 1)
vis[1] = 0
q = [1]
while q:
	u = q.pop(0)
	for v in range(1, n + 1):
		if graph[u][v] != graph[1][n] and vis[v] == -1:
			vis[v] = vis[u] + 1
			q.append(v)
print(vis[-1])


def main():
	(n, m) = list(map(int, input().split()))
	vrtxs = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = list(map(int, input().split()))
		u -= 1
		v -= 1
		vrtxs[u].append(v)
		vrtxs[v].append(u)
	if n - 1 in vrtxs[0]:
		for (u, l) in enumerate(vrtxs):
			tmp = [True] * n
			for v in l:
				tmp[v] = False
			tmp[u] = False
			vrtxs[u] = [v for (v, f) in enumerate(tmp) if f]
	(avail, nxt, t) = ([True] * n, [n - 1], 0)
	while nxt:
		(cur, nxt) = (nxt, [])
		t += 1
		for u in cur:
			for v in vrtxs[u]:
				if avail[v]:
					if not v:
						print(t)
						return
					avail[v] = False
					nxt.append(v)
	print(-1)

def __starting_point():
	main()
__starting_point()


(towns, railways) = [int(x) for x in input().split()]
u = [[] for x in range(towns + 1)]
t = [[] for x in range(towns + 1)]
for i in range(railways):
	[a, b] = [int(x) for x in input().split()]
	u[a].append(b)
	u[b].append(a)
for i in range(1, towns + 1):
	for j in range(i + 1, towns + 1):
		if j not in u[i]:
			t[i].append(j)
			t[j].append(i)

def bfs(g, n):
	q = [1]
	vis = [1 for x in range(n + 1)]
	dis = [0 for x in range(n + 1)]
	while len(q):
		cur = q[0]
		q.remove(cur)
		for i in g[cur]:
			if vis[i]:
				q.append(i)
				vis[i] = 0
				dis[i] = dis[cur] + 1
				if i == n:
					return dis[n]
	return -1
if towns in u[1]:
	print(bfs(t, towns))
else:
	print(bfs(u, towns))


import heapq as hq
(n, m) = map(int, input().split())
graph = [[0] * n for i in range(n)]
vertex = [i for i in range(0, n)]
total = []
for i in range(n):
	graph[i][i] = -1

def connect_vertex(u, v):
	if u != v:
		u = u - 1
		v = v - 1
		graph[u][v] = 1
		graph[v][u] = 1

def Dijkastra(u, v, sel):
	distance = [(0, u)]
	l = [u]
	d = {}
	while len(distance) != 0:
		(a, v1) = hq.heappop(distance)
		hq.heappop(l)
		d.update({v1: a})
		ind = vertex.index(v1)
		if v1 == v:
			return a
		for i in range(n):
			if graph[ind][i] == sel:
				if vertex[i] not in d:
					if vertex[i] not in l:
						hq.heappush(distance, (a + 1, vertex[i]))
						l.append(vertex[i])
					else:
						total_cost = a + 1
						for j in distance:
							if j[1] == vertex[i]:
								if j[0] > total_cost:
									j[0] = total_cost
								break
	if n - 1 not in d:
		return -1
	else:
		a = d[n - 1]
		return a[0]
for _ in range(m):
	(u, v) = map(int, input().split())
	connect_vertex(u, v)
if graph[0][-1] == 0:
	print(Dijkastra(0, n - 1, 1))
else:
	print(Dijkastra(0, n - 1, 0))


import sys
from collections import deque
(n, m) = map(int, input().split())
g = set()
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g |= {(x, y), (y, x)}
cut = (0, n - 1) in g
q = deque()
q.append(0)
d = [-1] * n
d[0] = 0
while len(q):
	x = q.popleft()
	for y in range(n):
		if cut ^ ((x, y) in g) and (d[y] == -1 or d[y] > d[x] + 1):
			d[y] = d[x] + 1
			q.append(y)
print(d[n - 1])


(n, m) = list(map(int, input().split(' ')))
road_adjacency_list = [set([]) for x in range(n + 1)]
for i in range(m):
	(a, b) = list(map(int, input().split(' ')))
	road_adjacency_list[a].add(b)
	road_adjacency_list[b].add(a)
railway_adjacency_list = [[] for x in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if i != j and j not in road_adjacency_list[i]:
			railway_adjacency_list[i].append(j)

def find_shortest(n, start, destination, adjacency_list):
	queue = [(start, 0)]
	visited = [False for i in range(n + 1)]
	visited[start] = True
	while queue != []:
		V = queue[0]
		if V[0] == destination:
			return V[1]
		for neig in adjacency_list[V[0]]:
			if not visited[neig]:
				visited[neig] = True
				queue.append((neig, V[1] + 1))
		del queue[0]
	return False
by_train = find_shortest(n, 1, n, railway_adjacency_list)
by_bus = find_shortest(n, 1, n, road_adjacency_list)
if by_train and by_bus:
	print(max(by_train, by_bus))
else:
	print(-1)


from queue import Queue
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
g1 = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
for i in range(n - 1):
	for j in range(i + 1, n):
		if j not in g[i]:
			g1[i].append(j)
			g1[j].append(i)
un = float('inf')

def bfs(g):
	q = Queue(maxsize=n)
	q.put(0)
	while not q.empty():
		curr = q.queue[0]
		q.get()
		for j in g[curr]:
			if dist[j] == un:
				dist[j] = dist[curr] + 1
				q.put(j)
	return dist[n - 1]
dist = [0] + [un] * (n - 1)
r = []
y = bfs(g)
dist = [0] + [un] * (n - 1)
z = bfs(g1)
r.extend([y, z])
if un in r:
	print(-1)
else:
	print(max(r))


(n, m) = map(int, input().split())
rail = [[False for v in range(n)] for u in range(n)]
road = [[True for v in range(n)] for u in range(n)]
for i in range(m):
	(u, v) = map(lambda x: x - 1, map(int, input().split()))
	rail[u][v] = rail[v][u] = True
	road[u][v] = road[v][u] = False
(source, target) = (0, n - 1)
if rail[source][target]:
	g = road
else:
	g = rail
seen = [False for v in range(n)]
queue = [(source, 0)]
tail = 0
while tail < len(queue):
	(u, steps) = queue[tail]
	tail += 1
	for v in range(n):
		if g[u][v] and (not seen[v]):
			if v == target:
				print(steps + 1)
				import sys
				sys.exit()
			seen[v] = True
			queue.append((v, steps + 1))
print(-1)


(n, m) = map(int, input().split())
q = [0]
graph = [[0] * n for i in range(n)]
dist = [-1] * n
dist[0] = 0
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u - 1][v - 1] = 1
	graph[v - 1][u - 1] = 1
while q:
	temp = q.pop(0)
	for i in range(n):
		if graph[temp][i] != graph[0][n - 1] and dist[i] == -1:
			dist[i] = dist[temp] + 1
			q.append(i)
print(dist[n - 1])


def bfs(g, n):
	q = [1]
	vis = [1 for x in range(n + 1)]
	dis = [0 for x in range(n + 1)]
	while len(q):
		cur = q[0]
		q.remove(cur)
		for i in g[cur]:
			if vis[i]:
				q.append(i)
				vis[i] = 0
				dis[i] = dis[cur] + 1
				if i == n:
					return dis[n]
	return -1
[n, m] = [int(x) for x in input().split()]
railway = [[] for x in range(n + 1)]
road = [[] for x in range(n + 1)]
for i in range(m):
	[a, b] = [int(x) for x in input().split()]
	railway[a].append(b)
	railway[b].append(a)
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if j not in railway[i]:
			road[i].append(j)
			road[j].append(i)
if n in railway[1]:
	print(bfs(road, n))
else:
	print(bfs(railway, n))


from collections import deque

def bfs(atual, adj, obj):
	res = -1
	vis = set([])
	fila = deque([])
	if 1 in adj:
		fila.append(1)
	nivel = [1000000] * (n + 1)
	nivel[1] = 0
	while fila:
		atual = fila.popleft()
		if atual == obj:
			res = nivel[atual]
			break
		if not atual in vis:
			for i in adj[atual]:
				if nivel[i] > nivel[atual] + 1:
					nivel[i] = nivel[atual] + 1
				fila.append(i)
		vis.add(atual)
	return res
(n, m) = input().split()
n = int(n)
m = int(m)
adjF = {}
adjR = {}
for i in range(m):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	if not a in adjF:
		adjF[a] = set([])
	if not b in adjF:
		adjF[b] = set([])
	adjF[a].add(b)
	adjF[b].add(a)
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if not i in adjF or not j in adjF[i]:
			if not i in adjR:
				adjR[i] = set([])
			if not j in adjR:
				adjR[j] = set([])
			adjR[i].add(j)
			adjR[j].add(i)
res1 = bfs(1, adjF, n)
res2 = bfs(1, adjR, n)
if res1 != -1 and res2 != -1:
	if res1 > res2:
		print(res1)
	else:
		print(res2)
else:
	print(-1)


import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from queue import Queue
from heapq import heappush, heappop, heapify, nlargest, nsmallest

def STR():
	return list(input())

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

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

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

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

def sortListWithIndex(listOfTuples, idx):
	return sorted(listOfTuples, key=lambda x: x[idx])

def sortDictWithVal(passedDic):
	temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
	toret = {}
	for tup in temp:
		toret[tup[0]] = tup[1]
	return toret

def sortDictWithKey(passedDic):
	return dict(OrderedDict(sorted(passedDic.items())))
INF = float('inf')
mod = 10 ** 9 + 7

def bfs(graph, veh):
	used = [False] * (n + 1)
	used[1] = True
	q = deque([(1, 0)])
	while len(q) > 0:
		popped = q.popleft()
		v = popped[0]
		dis = popped[1]
		if v == n:
			return dis
		if veh == 1:
			for w in graph[v]:
				if not used[w]:
					used[w] = True
					q.append((w, dis + 1))
		else:
			for w in range(1, n + 1):
				if not used[w] and w not in graph[v]:
					used[w] = True
					q.append((w, dis + 1))
	return -1
(n, m) = MAP()
graph = defaultdict(set)
for _ in range(m):
	(x, y) = MAP()
	graph[x].add(y)
	graph[y].add(x)
dst1 = bfs(graph, 1)
dst2 = bfs(graph, 0)
if dst1 == -1 or dst2 == -1:
	print(-1)
else:
	print(max(dst1, dst2))


(n, m) = [int(x) for x in input().split()]
busadjacency = []
trainadjacency = []
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		busadjacency.append((i, j))
trainadjacency = set()
for i in range(m):
	(a, b) = sorted([int(x) for x in input().split()])
	trainadjacency.add((a, b))
for i in range(len(busadjacency)):
	if busadjacency[i] in trainadjacency:
		busadjacency[i] = -1
busadj = [[] for i in range(n + 1)]
for i in range(len(busadjacency)):
	if busadjacency[i] != -1:
		busadj[busadjacency[i][0]].append(busadjacency[i][1])
		busadj[busadjacency[i][1]].append(busadjacency[i][0])
trainadj = [[] for i in range(n + 1)]
trainadjacency = sorted(trainadjacency)
for i in range(len(trainadjacency)):
	trainadj[trainadjacency[i][0]].append(trainadjacency[i][1])
	trainadj[trainadjacency[i][1]].append(trainadjacency[i][0])
busdist = [-1 for u in range(n + 1)]
busvis = [False for u in range(n + 1)]
busdist[1] = 0
busfrontier = [1]
ptr = 0
while ptr < len(busfrontier):
	u = busfrontier[ptr]
	if not busvis[u]:
		busvis[u] = True
		for v in busadj[u]:
			if not busvis[v]:
				if busdist[v] == -1:
					busdist[v] = busdist[u] + 1
				busfrontier.append(v)
	ptr += 1
traindist = [-1 for u in range(n + 1)]
trainvis = [False for u in range(n + 1)]
traindist[1] = 0
trainfrontier = [1]
ptr = 0
while ptr < len(trainfrontier):
	u = trainfrontier[ptr]
	if not trainvis[u]:
		trainvis[u] = True
		for v in trainadj[u]:
			if not trainvis[v]:
				if traindist[v] == -1:
					traindist[v] = traindist[u] + 1
				trainfrontier.append(v)
	ptr += 1
if traindist[n] == -1 or busdist[n] == -1:
	print(-1)
else:
	print(max(traindist[n], busdist[n]))


(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append([0] * n)
for i in range(m):
	(u, v) = map(int, input().split())
	l[u - 1][v - 1] = l[v - 1][u - 1] = 1
b = [-1] * n
b[0] = 0
q = [0]
while q:
	aux = q.pop(0)
	for i in range(n):
		if l[aux][i] != l[0][n - 1] and b[i] == -1:
			b[i] = b[aux] + 1
			q.append(i)
print(b[n - 1])


BUS_STEP = 0
RAIL_STEP = 1
INFINITY = 40000

def is_allowed(forbidden_path, town_index, step_index):
	if len(forbidden_path) < step_index + 1:
		return True
	if forbidden_path[step_index] != town_index:
		return True
	else:
		return False

def calculate_path(trace_back, start, end):
	if trace_back[end] is None:
		return None
	path = []
	current_step = end
	while True:
		path.append(current_step)
		current_step = trace_back[current_step]
		if current_step == start:
			path.append(current_step)
			break
	return path[::-1]

def shortest_path(matrix, foot_step, start, end, n, forbidden):
	town_costs = [INFINITY] * n
	trace_back = [None] * n
	town_costs[start] = 0
	next_queue = [start]
	while len(next_queue) != 0:
		path_queue = next_queue
		next_queue = []
		for u in path_queue:
			for v in range(n):
				if v == u:
					continue
				if matrix[u][v] == foot_step:
					if is_allowed(forbidden_path=forbidden, town_index=v, step_index=town_costs[u] + 1):
						if town_costs[v] > town_costs[u] + 1:
							town_costs[v] = town_costs[u] + 1
							trace_back[v] = u
							next_queue.append(v)
							if v == end:
								break
	return calculate_path(trace_back=trace_back, start=start, end=end)

def get_max_path_length(matrix, first_step, second_step, start, end, n):
	first_path = shortest_path(matrix, first_step, start, end, n, forbidden=[])
	if first_path is None:
		return INFINITY
	second_path = shortest_path(matrix, second_step, start, end, n, forbidden=first_path)
	if second_path is None:
		return INFINITY
	return max(len(first_path), len(second_path))

def main():
	(n, m) = [int(t) for t in input().split()]
	matrix = []
	for _ in range(n):
		matrix.append([BUS_STEP] * n)
	for _ in range(m):
		(u, v) = [int(t) - 1 for t in input().split()]
		matrix[u][v] = matrix[v][u] = RAIL_STEP
	bus_first = get_max_path_length(matrix, first_step=BUS_STEP, second_step=RAIL_STEP, start=0, end=n - 1, n=n)
	rail_first = get_max_path_length(matrix, first_step=RAIL_STEP, second_step=BUS_STEP, start=0, end=n - 1, n=n)
	optimal_path_length = min(bus_first, rail_first)
	if optimal_path_length >= INFINITY:
		print(-1)
	else:
		print(optimal_path_length - 1)
main()


(n, m) = map(int, input().split())
p = []
for i in range(n):
	p.append([])
for i in range(m):
	(a, b) = map(int, input().split())
	p[a - 1].append(b - 1)
	p[b - 1].append(a - 1)
pos = [-1] * n
k = [0]
pos[0] = 0
ans = -1
if n - 1 in p[0]:
	pos = [-1] * n
	k = [0]
	pos[0] = 0
	ans = -1
	while len(k) != 0:
		q = k.pop(0)
		if n - 1 not in p[q]:
			ans = pos[q] + 1
			break
		else:
			for i in range(n):
				if i not in p[q] and pos[i] == -1:
					k.append(i)
					pos[i] = pos[q] + 1
else:
	while len(k) != 0:
		q = k.pop(0)
		if n - 1 in p[q]:
			ans = pos[q] + 1
			break
		else:
			for i in range(len(p[q])):
				if pos[p[q][i]] == -1:
					k.append(p[q][i])
					pos[p[q][i]] = pos[q] + 1
print(ans)


from collections import deque
(n, m) = map(int, input().split())
nodes = list()
for i in range(n):
	nodes.append(set())
use_roads = False
for i in range(m):
	(rails_from, rails_to) = map(int, input().split())
	if (rails_from, rails_to) == (1, n) or (rails_from, rails_to) == (n, 1):
		use_roads = True
	nodes[rails_from - 1].add(rails_to - 1)
	nodes[rails_to - 1].add(rails_from - 1)
if use_roads:
	for (i_node, node) in enumerate(nodes):
		nodes[i_node] = set(range(n)) - node - {i_node}
q = deque()
q.append(0)
width = len(q)
depth = 0
while True:
	try:
		if len(q) == 0:
			print(-1)
			exit(0)
		if width == 0:
			depth += 1
			width = len(q)
		i_node = q.popleft()
		width -= 1
		if i_node == n - 1:
			print(depth)
			exit(0)
		for node in nodes[i_node]:
			q.append(node)
		nodes[i_node].clear()
	except Exception as ex:
		print(ex)


from heapq import *

def short(v, g, u, d):
	heap = []
	u[v] = True
	d[0] = 0
	heappush(heap, (0, v))
	while heap:
		(w, v) = heappop(heap)
		u[v] = True
		heap.clear()
		for i in g[v]:
			if not u[i]:
				if w + 1 < d[i]:
					d[i] = w + 1
					heappush(heap, (d[i], i))

def bfs(v, g, u, d):
	l = 0
	u[v] = True
	q = [(v, 0)]
	while q:
		(v, l) = q.pop(0)
		for i in g[v]:
			if not u[i]:
				q.append((i, l + 1))
				u[i] = True
				d[i] = l + 1
(n, m) = map(int, input().split())
a = {}
b = {}
for i in range(n):
	a[i] = [int(x) for x in range(n)]
	b[i] = []
for i in range(m):
	(u, v) = map(int, input().split())
	b[u - 1].append(v - 1)
	b[v - 1].append(u - 1)
	a[u - 1].remove(v - 1)
	a[v - 1].remove(u - 1)
u_a = [False] * n
u_b = [False] * n
d_a = [500000] * n
d_b = [500000] * n
bfs(0, a, u_a, d_a)
bfs(0, b, u_b, d_b)
if d_a[n - 1] == 500000 or d_b[n - 1] == 500000:
	print(-1)
else:
	print(max(d_a[n - 1], d_b[n - 1]))


(n, m) = map(int, input().split())
b = [[j for j in range(1, n + 1) if j != i + 1] for i in range(n)]
b.insert(0, [])
t = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	b[u].remove(v)
	b[v].remove(u)
	t[u].append(v)
	t[v].append(u)

def find_shorteset_path(n, start, des, adj):
	queue = [(start, 0)]
	visited = [False for i in range(n + 1)]
	visited[start] = True
	while queue != []:
		v = queue[0]
		if v[0] == des:
			return v[1]
		for neig in adj[v[0]]:
			if not visited[neig]:
				visited[neig] = True
				queue.append((neig, v[1] + 1))
		del queue[0]
	return False
bus_sol = find_shorteset_path(n, 1, n, b)
train_sol = find_shorteset_path(n, 1, n, t)
if train_sol and bus_sol:
	print(max(train_sol, bus_sol))
else:
	print(-1)


def read_data():
	(n, m) = map(int, input().split())
	Es = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		Es[u].append(v)
		Es[v].append(u)
	return (n, m, Es)

def solve(n, m, Es):
	if n - 1 not in Es[0]:
		return shortestpath(n, Es)
	else:
		Es = trans(n, Es)
		return shortestpath(n, Es)

def trans(n, Es):
	Emat = [[False] * n for i in range(n)]
	for (i, row) in enumerate(Es):
		for j in row:
			Emat[i][j] = True
	nEs = [[] for i in range(n)]
	for u in range(n):
		for v in range(n):
			if u == v:
				continue
			if Emat[u][v]:
				continue
			nEs[u].append(v)
	return nEs

def shortestpath(n, Es):
	visited = [False] * n
	visited[0] = True
	steps = 0
	fs = [0]
	while fs:
		nfs = []
		for f in fs:
			if f == n - 1:
				return steps
			for v in Es[f]:
				if visited[v]:
					continue
				nfs.append(v)
				visited[v] = True
		fs = nfs
		steps += 1
	return -1
(n, m, Es) = read_data()
print(solve(n, m, Es))


def menorTempo(array, n):
	var1 = 3 - array[1][n]
	array_aux = [0] * (n + 1)
	d = [n + 1] * (n + 1)
	resultado = d[1] = 0
	i = 1
	while i != n:
		array_aux[i] = 1
		for j in range(1, n + 1):
			if array_aux[j] == 0:
				if array[i][j] == var1:
					if d[j] > d[i] + 1:
						d[j] = d[i] + 1
		aux = n + 1
		for j in range(1, n + 1):
			if array_aux[j] == 0 and d[j] < aux:
				aux = d[j]
				i = j
		if aux == n + 1:
			return -1
		elif i == n:
			return d[n]
	return resultado

def main():
	entrada = input().split()
	n = int(entrada[0])
	m = int(entrada[1])
	array = [0] * (n + 1)
	for i in range(n + 1):
		array[i] = [1] * (n + 1)
	for i in range(m):
		entrada = input().split()
		a = int(entrada[0])
		b = int(entrada[1])
		array[a][b] = 2
		array[b][a] = 2
	print(menorTempo(array, n))
main()


(n, m) = map(int, input().split())
d = [[0 for col in range(500)] for lin in range(500)]
vet = [0] * 500
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	d[x][y] = 1
	d[y][x] = 1
q = [0]
l = 0
while l < len(q):
	for i in range(1, n):
		if d[0][n - 1] != d[q[l]][i] and vet[i] == 0:
			vet[i] = vet[q[l]] + 1
			q.append(i)
	l += 1
if vet[n - 1] == 0:
	print('-1')
else:
	print(vet[n - 1])


(ex, ey) = map(int, input().split())
c = [0] * (ex + 1)
for l in range(ex + 1):
	c[l] = [1] * (ex + 1)
for i in range(ey):
	(a, b) = map(int, input().split())
	c[a][b] = c[b][a] = 2
(x, v, i) = (3 - c[1][ex], [0] * (ex + 1), 1)
d = [ex + 1] * (ex + 1)
time = d[1] = 0
while i != ex:
	v[i] = 1
	for j in range(1, ex + 1):
		if v[j] == 0 and c[i][j] == x and (d[j] > d[i] + 1):
			d[j] = d[i] + 1
	m = ex + 1
	for j in range(1, ex + 1):
		if v[j] == 0 and d[j] < m:
			m = d[j]
			i = j
	if m == ex + 1:
		time = -1
		break
	elif i == ex:
		time = d[ex]
		break
print(time)


(n, m) = map(int, input().split())
k = n + 1
pos = [[0] * k for _ in range(k)]
dis = [-1] * k
dis[1] = 0
aux = [1]
for _ in range(m):
	(u, v) = map(int, input().split())
	pos[u][v] = pos[v][u] = 1
while aux:
	u = aux.pop(0)
	for v in range(1, k):
		if pos[u][v] != pos[1][n] and dis[v] == -1:
			dis[v] = dis[u] + 1
			aux.append(v)
res = dis[n]
print(res)


from collections import defaultdict as dfdict

def bfs(G, rail_connected=False):
	level = [1]
	visited = set([1])
	cnt = 0
	while len(level) > 0:
		nxtlevel = []
		for i in level:
			nxt = G[i] if not rail_connected else all_vertice - G[i]
			for j in nxt:
				if j not in visited:
					if j == n:
						cnt += 1
						return cnt
					else:
						nxtlevel.append(j)
						visited.add(j)
		level = nxtlevel
		cnt += 1
	return -1
(n, m) = [int(i) for i in input().split()]
rails = dfdict(set)
all_vertice = set([i + 1 for i in range(n)])
for _ in range(m):
	(xt, yt) = [int(i) for i in input().split()]
	rails[xt].add(yt)
	rails[yt].add(xt)
R = False
if n in rails[1]:
	R = True
else:
	R = False
print(bfs(rails, R))


from collections import defaultdict
from collections import deque
import sys

def bfs(graph, node, inverted, target):
	q = deque()
	q.append(node)
	distance = {}
	distance[node] = 0
	while len(q) > 0:
		current_node = q.popleft()
		if inverted:
			succ = set(range(1, target + 1)) - set(graph[current_node])
		else:
			succ = graph[current_node]
		for children in succ:
			if children not in distance.keys():
				distance[children] = distance[current_node] + 1
				q.append(children)
	if target in distance.keys():
		return distance[target]
	return -1
input_file = sys.stdin
(nodes, roads) = map(int, input_file.readline().rstrip().split())
graph = defaultdict(list)
for line in input_file.readlines():
	(source, target) = map(int, line.rstrip().split())
	graph[source].append(target)
	graph[target].append(source)
q = deque()
if nodes in graph[1]:
	print(bfs(graph, 1, True, nodes))
else:
	print(bfs(graph, 1, False, nodes))


from collections import defaultdict
(n, m) = map(int, input().split())
temp = set([i for i in range(1, n + 1)])
railway = defaultdict(list)
for _ in range(m):
	(u, v) = map(int, input().split())
	railway[u].append(v)
	railway[v].append(u)
roads = defaultdict(list)
for i in range(1, n + 1):
	curr = set(railway[i])
	curr = temp.difference(curr)
	curr.remove(i)
	roads[i] = list(curr)
railway_trav = -1
queue = [[1, 0]]
visited = [False for i in range(n + 1)]
visited[1] = True
while queue != []:
	(node, dist) = queue[0]
	queue.pop(0)
	if node == n:
		railway_trav = dist
		break
	for child in railway[node]:
		if not visited[child]:
			visited[child] = True
			queue.append([child, dist + 1])
roads_trav = -1
queue = [[1, 0]]
visited = [False for i in range(n + 1)]
visited[1] = True
while queue != []:
	(node, dist) = queue[0]
	queue.pop(0)
	if node == n:
		roads_trav = dist
		break
	for child in roads[node]:
		if not visited[child]:
			visited[child] = True
			queue.append([child, dist + 1])
if roads_trav == -1 or railway_trav == -1:
	print(-1)
else:
	print(max(1, roads_trav, railway_trav))


(n, m) = map(int, input().split())
graphrail = [[] for i in range(n)]
graphroad = [[] for i in range(n)]
dic = [[0] * n for i in range(n)]

def bfs(graph, s):
	level = {s + 1: 0}
	front = [s + 1]
	i = 1
	while front:
		next = []
		for u in front:
			for v in graph[u - 1]:
				if v not in level:
					level[v] = i
					next.append(v)
		front = next
		i += 1
	if n in level:
		return level[n]
	else:
		return -1
for i in range(m):
	(x, y) = map(int, input().strip().split())
	dic[x - 1][y - 1] = 1
	dic[y - 1][x - 1] = 1
	graphrail[x - 1].append(y)
	graphrail[y - 1].append(x)
for i in range(n):
	for j in range(n):
		if dic[i][j] == 0 and i != j:
			graphroad[i].append(j + 1)
x = bfs(graphroad, 0)
y = bfs(graphrail, 0)
if x == -1 or y == -1:
	print(-1)
else:
	print(max(x, y))


def bfs(x):
	ans = 0
	visited = set()
	nex = set()
	for i in range(n):
		if mat[0][i] == x:
			visited.add(i)
			nex.add(i)
	if len(nex) > 0:
		ans += 1
	while len(nex) != 0 and n - 1 not in visited:
		nnex = set()
		for node in nex:
			for i in range(n):
				if mat[node][i] == x:
					if i not in visited:
						visited.add(i)
						nnex.add(i)
		nex = set(nnex)
		if len(nex) > 0:
			ans += 1
	return ans if ans != 0 and n - 1 in visited else -1
(n, m) = [int(__) for __ in input().strip().split()]
mat = [[1 if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b) = [int(__) for __ in input().strip().split()]
	a -= 1
	b -= 1
	mat[a][b] = 0
	mat[b][a] = 0
if mat[0][n - 1] == 0:
	print(bfs(1))
else:
	print(bfs(0))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from types import GeneratorType
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')
import time
start_time = time.time()
import collections as col
import math
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

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

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

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

def solve():
	rail = col.defaultdict(set)
	road = col.defaultdict(set)
	(N, M) = getInts()
	nodes = set()
	for i in range(1, N + 1):
		for j in range(i + 1, N + 1):
			nodes.add((i, j))
	for m in range(M):
		(U, V) = getInts()
		if U > V:
			(U, V) = (V, U)
		nodes.remove((U, V))
		rail[U].add(V)
		rail[V].add(U)
	for (U, V) in nodes:
		road[U].add(V)
		road[V].add(U)

	def bfs(graph, start, end):
		visited = set()
		visited.add(start)
		queue = [(start, 0)]
		queue = col.deque(queue)
		while queue:
			(node, level) = queue.popleft()
			for neighbour in graph[node]:
				if neighbour not in visited:
					visited.add(neighbour)
					queue.append((neighbour, level + 1))
					if neighbour == N:
						return level + 1
		return -1
	if N in road[1]:
		return bfs(rail, 1, N)
	return bfs(road, 1, N)
print(solve())


(num_cidades, num_ferrovias) = map(int, input().split())
grafo = [[0] * num_cidades for i in range(num_cidades)]
for i in range(num_ferrovias):
	(ferrovia_inicio, ferrovia_fim) = map(int, input().split())
	grafo[ferrovia_inicio - 1][ferrovia_fim - 1] = 1
	grafo[ferrovia_fim - 1][ferrovia_inicio - 1] = 1
aux = [0]
i = 0
cidade_u = [-1] * num_cidades
cidade_u[0] = 0
while i < len(aux):
	cidade_v = aux[i]
	i += 1
	for j in range(num_cidades):
		if cidade_u[j] == -1 and grafo[cidade_v][j] != grafo[0][num_cidades - 1]:
			cidade_u[j] = cidade_u[cidade_v] + 1
			aux.append(j)
print(cidade_u[num_cidades - 1])


from heapq import *
(n, m) = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
G = [[] for _ in range(n)]
R = [[] for _ in range(n)]
for k in range(m):
	G[L[k][0] - 1] += [L[k][1] - 1]
	G[L[k][1] - 1] += [L[k][0] - 1]
for i in range(n - 1):
	for j in range(i + 1, n):
		if j not in G[i]:
			R[i] += [j]
			R[j] += [i]
weightG = [[1 for _ in range(n)] for k in range(n)]
weightR = [[1 for _ in range(n)] for k in range(n)]

def aux(graph, weight):
	source = 0
	n = len(graph)
	dist = [float('inf')] * n
	prec = [None] * n
	marked = [False] * n
	dist[source] = 0
	heap = [(0, source)]
	while heap:
		(_, node) = heappop(heap)
		if not marked[node]:
			marked[node] = True
			for neighbor in graph[node]:
				my_dist_neighbor = dist[node] + weight[node][neighbor]
				if my_dist_neighbor < dist[neighbor]:
					dist[neighbor] = my_dist_neighbor
					prec[neighbor] = node
					heappush(heap, (my_dist_neighbor, neighbor))
	return (dist, prec)

def pred(L):
	R = [n - 1]
	s = n - 1
	while s > 0:
		s = L[s]
		R = [s] + R
	return R

def resolution(G, R, weightG, weightR):
	(dG, pG) = aux(G, weightG)
	(dR, pR) = aux(R, weightR)
	if pG[n - 1] == None or pR[n - 1] == None:
		return -1
	else:
		LG = pred(pG)
		LR = pred(pR)
		k = 1
		lm = min([len(LG), len(LR)])
		while k < lm and LG[k] != LR[k]:
			k += 1
		if k == lm:
			return max([dG[n - 1], dR[n - 1]])
		else:
			weightG[pG[LG[k]]][LG[k]] = 3
			sol1 = resolution(G, R, weightG, weightR)
			if sol1 == -1:
				sol1 = 1337
			weightR[pR[LR[k]]][LR[k]] = 3
			weightG[pG[LG[k]]][LG[k]] = 1
			sol2 = resolution(G, R, weightG, weightR)
			if sol2 == -1:
				sol2 = 1337
			sol = max([sol1, sol2])
			if sol == 1337:
				return -1
			else:
				return sol
print(resolution(G, R, weightG, weightR))


(n, m) = tuple(map(int, input().split()))
g = [[n * n] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(u, v) = tuple(map(int, input().split()))
	g[u][v] = g[v][u] = 1
if g[1][n] == 1:
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			g[i][j] = n * n + 1 - g[i][j]
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
print(-1 if g[1][n] == n * n else g[1][n])


from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
g = [[0] * n for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1][v - 1] = 1
	g[v - 1][u - 1] = 1
q = [0]
r = 0
u = [-1] * n
u[0] = 0
while r < len(q):
	v = q[r]
	r += 1
	for i in range(n):
		if u[i] == -1 and g[v][i] != g[0][n - 1]:
			u[i] = u[v] + 1
			q.append(i)
print(u[n - 1])


(n, m) = map(int, input().split())
arr = [[0] * n for i in range(n)]
arr2 = [-1] * n
arr2[0] = 0
arr3 = []
for i in range(m):
	(a, b) = map(int, input().split())
	arr[b - 1][a - 1] = 1
	arr[a - 1][b - 1] = 1
arr3.append(0)
while arr3:
	i = arr3.pop(0)
	for j in range(n):
		if arr[i][j] != arr[0][n - 1] and arr2[j] == -1:
			arr2[j] = arr2[i] + 1
			arr3.append(j)
print(arr2[n - 1])


from queue import Queue
import sys

def __starting_point():

	def bfs(flag):
		vis = set()
		vis |= {1}
		q = Queue()
		q.put((1, 0))
		while not q.empty():
			(u, dis) = q.get()
			for v in range(1, n + 1):
				if v not in vis and ((u, v) in h) == flag:
					vis |= {v}
					q.put((v, dis + 1))
					if v == n:
						return dis + 1
		return -1
	(n, m) = list(map(int, input().split()))
	h = set()
	for _ in range(0, m):
		(x, y) = list(map(int, input().split()))
		h |= {(x, y)}
		h |= {(y, x)}
	dist1 = bfs(True)
	dist2 = bfs(False)
	if dist1 == -1 or dist2 == -1:
		print(-1)
	else:
		print(max(dist1, dist2))
__starting_point()


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

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

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def init():
	G = defaultdict(list)

	def addEdge(a, b):
		G[a].append(b)
		G[b].append(a)
	H = defaultdict(list)

	def bfs(R, n):
		d = deque()
		vis = [False] * (n + 1)
		d.append((1, 0))
		vis[1] = True
		while d:
			(x, y) = d.popleft()
			if x == n:
				return y
			for i in R.get(x, []):
				if not vis[i]:
					vis[i] = True
					d.append((i, y + 1))
		print(-1)
		exit(0)
	(n, m) = aj()
	city = {i for i in range(1, n + 1)}
	for i in range(m):
		(u, v) = aj()
		addEdge(u, v)
	for i in range(1, n + 1):
		H[i] = city - set(G.get(i, []))
	print(max(bfs(G, n), bfs(H, n)))
init()


def bsf(graph, n):
	queue = [0]
	visited = [False] * n
	visited[0] = True
	dist = [0] * n
	while len(queue):
		current = queue.pop(0)
		for i in graph[current]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True
				dist[i] = dist[current] + 1
	if dist[n - 1] != 0:
		return dist[n - 1]
	return -1
(n, m) = map(int, input().split())
graph = {}
for i in range(n):
	graph[i] = []
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
if n - 1 in graph[0]:
	for i in range(n):
		tmp_i = []
		for j in range(n):
			if j not in graph[i] and j != i:
				tmp_i.append(j)
		graph[i] = tmp_i
print(bsf(graph, n))


import queue
connect = [[0 for i in range(401)] for j in range(401)]

def bfs(val):
	q = queue.Queue()
	dis = [-1 for i in range(401)]
	dis[1] = 0
	q.put(1)
	while not q.empty():
		x = q.get()
		for i in range(1, n + 1):
			if connect[x][i] == val and dis[i] == -1:
				dis[i] = dis[x] + 1
				q.put(i)
	return dis[n]
temp = input().split()
n = int(temp[0])
m = int(temp[1])
dis = [[[0 for i in range(401)] for j in range(401)] for k in range(2)]
for i in range(m):
	temp = input().split()
	u = int(temp[0])
	v = int(temp[1])
	connect[u][v] = connect[v][u] = 1
print(bfs(1 - connect[1][n]))


(N, M) = [int(x) for x in input().split()]
train = [[False for b in range(N)] for a in range(N)]
for m in range(M):
	(a, b) = [int(x) - 1 for x in input().split()]
	train[a][b] = train[b][a] = True
if train[0][N - 1]:
	train = [[not train[a][b] for b in range(N)] for a in range(N)]
dist = [N + 1 for n in range(N)]
dist[0] = 0
from queue import Queue
Q = Queue()
Q.put(0)
while not Q.empty():
	kde = Q.get()
	for kam in range(N):
		if train[kde][kam]:
			if dist[kam] > dist[kde] + 1:
				dist[kam] = dist[kde] + 1
				Q.put(kam)
print(-1 if dist[N - 1] == N + 1 else dist[N - 1])


import math

def bfs(adj, tar):
	visited = []
	queue = [(1, 0)]
	while len(queue) > 0:
		(currI, currDist) = queue.pop(0)
		if not currI in visited:
			visited.append(currI)
			for i in adj[currI]:
				if i == tar:
					return currDist + 1
				if not i in visited:
					queue.append((i, currDist + 1))
	return -1
(n, m) = list(map(int, input().split()))
adj_rails = [[] for _ in range(n + 1)]
for i in range(m):
	(x, y) = list(map(int, input().split()))
	adj_rails[x].append(y)
	adj_rails[y].append(x)
adj_roads = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if i != j and (not j in adj_rails[i]):
			adj_roads[i].append(j)
d1 = bfs(adj_rails, n)
d2 = bfs(adj_roads, n)
if d1 == -1 or d2 == -1:
	print('-1')
else:
	print(max(d1, d2))


(cidade_x, cidade_y) = map(int, input().split())
cruzamento = [0] * (cidade_x + 1)
for l in range(cidade_x + 1):
	cruzamento[l] = [1] * (cidade_x + 1)
for i in range(cidade_y):
	(a, b) = map(int, input().split())
	cruzamento[a][b] = cruzamento[b][a] = 2
(x, veiculo, indice) = (3 - cruzamento[1][cidade_x], [0] * (cidade_x + 1), 1)
d = [cidade_x + 1] * (cidade_x + 1)
tempo_ultimo = d[1] = 0
while indice != cidade_x:
	veiculo[indice] = 1
	for j in range(1, cidade_x + 1):
		if veiculo[j] == 0 and cruzamento[indice][j] == x and (d[j] > d[indice] + 1):
			d[j] = d[indice] + 1
	menor = cidade_x + 1
	for j in range(1, cidade_x + 1):
		if veiculo[j] == 0 and d[j] < menor:
			menor = d[j]
			indice = j
	if menor == cidade_x + 1:
		tempo_ultimo = -1
		break
	elif indice == cidade_x:
		tempo_ultimo = d[cidade_x]
		break
print(tempo_ultimo)


from collections import deque
(n, m) = map(int, input().split())
a = [set() for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	a[x].add(y)
	a[y].add(x)
if n not in a[1]:
	t = True
else:
	t = False
q = deque()
q.append(1)
z = [-1 for i in range(n + 1)]
z[1] = 0
while len(q) > 0:
	v = q.popleft()
	for i in range(1, n + 1):
		if t ^ (i in a[v]):
			continue
		if z[i] == -1:
			z[i] = z[v] + 1
			q.append(i)
			if i == n:
				print(z[i])
				exit(0)
print(-1)


def bfs(mat):
	n = len(mat)
	q = [0]
	visited = [-1] * n
	visited[0] = 0
	while len(q) > 0:
		cur = q.pop(0)
		for i in range(n):
			if visited[i] == -1 and mat[cur][i] == 1:
				q.append(i)
				visited[i] = visited[cur] + 1
	return visited[n - 1]

def flip(mat):
	a = [1, 0]
	for i in range(len(mat)):
		for j in range(len(mat)):
			if i != j:
				mat[i][j] = a[mat[i][j]]

def main():
	(n, m) = [int(i) for i in input().split(' ')]
	mat = [[0] * n for i in range(n)]
	for i in range(m):
		(a, b) = [int(i) for i in input().split(' ')]
		a -= 1
		b -= 1
		(mat[a][b], mat[b][a]) = (1, 1)
	if mat[0][n - 1] == 1:
		flip(mat)
	print(bfs(mat))
main()


from queue import PriorityQueue
LIMIT = 1000000001

def dijkstra(graph, distances, visited):
	queue = PriorityQueue()
	queue.put((0, 1))
	distances[1] = 0
	while not queue.empty():
		(_, node) = queue.get()
		if visited[node]:
			continue
		visited[node] = True
		for i in range(len(graph[node])):
			(n, weight) = graph[node][i]
			if distances[n] > distances[node] + weight:
				distances[n] = distances[node] + weight
				queue.put((distances[n], n))
(n, m) = map(int, input().split())
graph = [[] for i in range(n + 1)]
d = {}
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u].append((v, 1))
	graph[v].append((u, 1))
	d[min(u, v), max(u, v)] = True
visited = [False] * (n + 1)
distance_r = [LIMIT] * (n + 1)
distance_b = [LIMIT] * (n + 1)
dijkstra(graph, distance_r, visited)
visited = [False] * (n + 1)
graph = [[] for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if (i, j) not in d:
			graph[i].append((j, 1))
			graph[j].append((i, 1))
dijkstra(graph, distance_b, visited)
if distance_b[n] == LIMIT or distance_r[n] == LIMIT:
	print(-1)
else:
	print(max(distance_b[n], distance_r[n]))


from collections import deque

def answer(n, g):
	vis = [0] * (n + 1)
	q = deque([(0, 1)])
	vis[1] = 1
	while q:
		item = q.popleft()
		node = item[1]
		wt = item[0]
		if node == n:
			return wt
		for v in range(1, n + 1):
			if g[node][v] > 0 and vis[v] == 0:
				vis[v] = 1
				q.append((wt + 1, v))
	return -1
(n, m) = map(int, input().split())
g = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	g[u][v] = 1
	g[v][u] = 1
if g[1][n] == 1:
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if g[i][j] == 1:
				g[i][j] = 0
			elif i != j:
				g[i][j] = 1
x = answer(n, g)
if x == -1:
	print(-1)
else:
	print(max(1, x))


import sys
from collections import deque

def bfs_search(adj_list, visited, queue, d, n, thrown):
	node = queue.popleft()
	if visited[node]:
		return False
	visited[node] = True
	for e in adj_list[node]:
		if visited[e] == False and thrown[e] == False:
			queue.append(e)
			thrown[e] = True
			d[e] = d[node] + 1
			if e == n:
				return True
	return False

def answer(n, m, u, v):
	if m == 0 or m == n * (n - 1) // 2:
		return -1
	adj_matrix = [[0 for j in range(n + 1)] for i in range(n + 1)]
	adj_list = [[] for _ in range(n + 1)]
	visited = [False for _ in range(n + 1)]
	rail_direct = False
	for i in range(m):
		adj_list[v[i]].append(u[i])
		adj_list[u[i]].append(v[i])
		adj_matrix[v[i]][u[i]] = 1
		adj_matrix[u[i]][v[i]] = 1
		if v[i] == 1 and u[i] == n or (v[i] == n and u[i] == 1):
			rail_direct = True
	if rail_direct:
		adj_list = [[] for _ in range(n + 1)]
		for i in range(1, n):
			for j in range(i + 1, n + 1):
				if adj_matrix[i][j] != 1:
					adj_list[i].append(j)
					adj_list[j].append(i)
	queue = deque([1])
	d = [500 for _ in range(n + 1)]
	thrown = [False for _ in range(n + 1)]
	d[1] = 0
	thrown[1] = True
	found = False
	while not found and len(queue) > 0:
		found = bfs_search(adj_list, visited, queue, d, n, thrown)
	if found:
		return d[n]
	return -1

def main():
	(n, m) = map(int, sys.stdin.readline().split())
	u = [0 for _ in range(m)]
	v = [0 for _ in range(m)]
	for i in range(m):
		(u[i], v[i]) = map(int, sys.stdin.readline().split())
	print(answer(n, m, u, v))
	return
main()


from collections import deque
(n, m) = map(int, input().split())
rail_network = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	rail_network[u][v] = rail_network[v][u] = 1
que = deque()
dis = [-1] * (n + 1)
dis[1] = 0
que.append(1)
while que:
	temp = que.popleft()
	for i in range(1, n + 1):
		if rail_network[temp][i] != rail_network[1][n] and dis[i] == -1:
			dis[i] = dis[temp] + 1
			que.append(i)
print(dis[-1])


class Graph:

	def __init__(self, v):
		self.v = v
		self.train = [[False for b in range(self.v)] for a in range(self.v)]
		self.bus = [[False for b in range(self.v)] for a in range(self.v)]

	def edge_train(self, u, v):
		self.train[u - 1][v - 1] = 1
		self.train[v - 1][u - 1] = 1

	def edge_bus(self):
		for i in range(self.v):
			for j in range(i, self.v):
				if i != j and self.train[i][j] != 1:
					self.bus[i][j] = 1
					self.bus[j][i] = 1

	def mindistance(self, dist, sptset):
		min = 10000
		min_index = -1
		for v in range(self.v):
			if dist[v] < min and sptset[v] == False:
				min = dist[v]
				min_index = v
		return min_index

	def dijkstra_train(self, src=0):
		dist = [10000] * self.v
		dist[src] = 0
		sptset = [False] * self.v
		for cout in range(self.v):
			u = self.mindistance(dist, sptset)
			sptset[u] = True
			for v in range(self.v):
				if self.train[u][v] > 0 and sptset[v] == False and (dist[v] > dist[u] + self.train[u][v]):
					dist[v] = dist[u] + self.train[u][v]
		return dist[self.v - 1]

	def dijkstra_bus(self, src=0):
		dist = [10000] * self.v
		dist[src] = 0
		sptset = [False] * self.v
		for cout in range(self.v):
			u = self.mindistance(dist, sptset)
			sptset[u] = True
			for v in range(self.v):
				if self.bus[u][v] > 0 and sptset[v] == False and (dist[v] > dist[u] + self.bus[u][v]):
					dist[v] = dist[u] + self.bus[u][v]
		return dist[self.v - 1]

	def print_ans(self):
		a = self.dijkstra_train()
		b = self.dijkstra_bus()
		if a == 10000 or b == 10000:
			print(-1)
		elif a > b:
			print(a)
		else:
			print(b)
(n, m) = map(int, input().split())
g = Graph(n)
for i in range(m):
	(x, y) = map(int, input().split())
	g.edge_train(x, y)
g.edge_bus()
g.print_ans()


(n, m) = map(int, input().split())
railway = [[] for i in range(n + 1)]
roads = [[] for i in range(n + 1)]
railway_direct = False
for i in range(m):
	(u, v) = map(int, input().split())
	if u == 1 and v == n or (u == n and v == 1):
		railway_direct = True
	railway[u].append(v)
	railway[v].append(u)
for i in range(1, n + 1):
	for k in range(i + 1, n + 1):
		if k not in railway[i]:
			roads[i].append(k)
			roads[k].append(i)

def shortest_path(graph, start, goal):
	explored = []
	queue = [[start]]
	if start == goal:
		return
	while queue:
		path = queue.pop(0)
		node = path[-1]
		if node not in explored:
			neighbours = graph[node]
			for neighbour in neighbours:
				new_path = list(path)
				new_path.append(neighbour)
				queue.append(new_path)
				if neighbour == goal:
					return len(new_path) - 1
			explored.append(node)
	return -1
if railway_direct:
	print(shortest_path(roads, 1, n))
else:
	print(shortest_path(railway, 1, n))


from collections import defaultdict
(n, m) = list(map(int, input().split()))
temp = set()
for i in range(n):
	temp.add(i)
graph = defaultdict(list)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u].append(v)
	graph[v].append(u)
road = defaultdict(list)
for i in range(n):
	arr = set(graph[i])
	arr = temp.difference(arr)
	arr.remove(i)
	road[i] = list(arr)
q = [[0, 0]]
ans = -1
visited = [False for i in range(n)]
visited[0] = True
while q != []:
	(node, dist) = (q[0][0], q[0][1])
	q.pop(0)
	if node == n - 1:
		ans = dist
		break
	for v in graph[node]:
		if visited[v] == False:
			visited[v] = True
			q.append([v, dist + 1])
temp = -1
q = [[0, 0]]
visited = [False for i in range(n)]
visited[0] = True
while q != []:
	(node, dist) = (q[0][0], q[0][1])
	q.pop(0)
	if node == n - 1:
		temp = dist
		break
	for v in road[node]:
		if visited[v] == False:
			visited[v] = True
			q.append([v, dist + 1])
if ans == -1 or temp == -1:
	print(-1)
else:
	print(max(1, ans, temp))


from collections import defaultdict
from collections import deque
(n, m) = map(int, input().split())
r = []
for i in range(n):
	r.append([0] * n)
for i in range(m):
	(x, y) = map(int, input().split())
	r[x - 1][y - 1] = 1
	r[y - 1][x - 1] = 1
d = defaultdict(list)
for i in range(n):
	for j in range(n):
		if r[i][j] != r[0][n - 1]:
			d[i].append(j)
visited = {}
q = deque()
q.append(0)
distance = {}
distance[0] = 0
visited[0] = 1
while q:
	x = q.popleft()
	for j in d[x]:
		if visited.get(j, 0) == 0:
			visited[j] = 1
			q.append(j)
			distance[j] = distance[x] + 1
if distance.get(n - 1, 0) == 0:
	print(-1)
else:
	print(distance[n - 1])


def bfs_shortest_path(graph, start, goal):
	explored = []
	queue = [[start]]
	while queue:
		path = queue.pop(0)
		node = path[-1]
		if node not in explored:
			neighbours = graph[node]
			for neighbour in neighbours:
				new_path = list(path)
				new_path.append(neighbour)
				queue.append(new_path)
				if neighbour == goal:
					return len(new_path) - 1
			explored.append(node)
	return -1
town_rail = input().split(' ')
town = int(town_rail[0])
rail = int(town_rail[1])
railways = []
graph = {}
for j in range(1, town + 1):
	graph[j] = []
for i in range(rail):
	railways.append(input().split(' '))
if ['1', str(town)] in railways or [str(town), '1'] in railways:
	for key in graph:
		for k in range(1, town + 1):
			if k != key:
				graph[key].append(k)
	for pair in railways:
		graph[int(pair[0])].remove(int(pair[1]))
		graph[int(pair[1])].remove(int(pair[0]))
else:
	for pair in railways:
		graph[int(pair[0])].append(int(pair[1]))
		graph[int(pair[1])].append(int(pair[0]))
print(bfs_shortest_path(graph, 1, town))


(n, m) = map(int, input().split())
mat = [[0] * 500 for i in range(500)]
d = [0] * 500
for i in range(m):
	(a, b) = map(int, input().split())
	mat[a][b] = 1
	mat[b][a] = 1
d[1] = 1
q = [1]
t = 0
if mat[1][n] == 1:
	t = 0
else:
	t = 1
while len(q) > 0:
	a = q[0]
	q.pop(0)
	for i in range(1, n + 1):
		if mat[a][i] == t and d[i] == 0:
			q.append(i)
			d[i] = d[a] + 1
print(d[n] - 1)


import sys
result = -1
(number_1, number_2) = map(int, input().split())
x = [[False for v in range(number_1)] for u in range(number_1)]
y = [[True for v in range(number_1)] for u in range(number_1)]
for index in range(number_2):
	(u, v) = map(lambda x: x - 1, map(int, input().split()))
	x[u][v] = x[v][u] = True
	y[u][v] = y[v][u] = False
(n, m) = (0, number_1 - 1)
if x[n][m]:
	g = y
else:
	g = x
seen = [False for u in range(number_1)]
seen[0] = True
vector = [(n, 0)]
tail = 0
while tail < len(vector):
	(u, steps) = vector[tail]
	tail += 1
	for v in range(number_1):
		if g[u][v] and (not seen[v]):
			if v == m:
				print(steps + 1)
				sys.exit()
			seen[v] = True
			vector.append((v, steps + 1))
print(result)


from heapq import heappush, heappop

def dijkstra(adjList, s):
	num = len(adjList)
	dist = [10 ** 8 for i in range(num)]
	prev = [-1 for i in range(num)]
	queue = []
	heappush(queue, (0, s))
	dist[s] = 0
	while queue != []:
		(v_cost, v) = heappop(queue)
		if dist[v] < v_cost:
			continue
		for (u_cost, u) in adjList[v]:
			if u != v and u_cost + dist[v] < dist[u]:
				prev[u] = v
				dist[u] = u_cost + dist[v]
				heappush(queue, (dist[u], u))
	return (dist, prev)

def dijkstra2(adjList, s, route):
	num = len(adjList)
	dist = [10 ** 8 for i in range(num)]
	queue = []
	heappush(queue, (0, s))
	dist[s] = 0
	while queue != []:
		(v_cost, v) = heappop(queue)
		if dist[v] < v_cost:
			continue
		for (u_cost, u) in adjList[v]:
			if u_cost + dist[v] < n and route[u_cost + dist[v]] == u:
				continue
			if u != v and u_cost + dist[v] < dist[u]:
				dist[u] = u_cost + dist[v]
				heappush(queue, (dist[u], u))
	return dist
(n, m) = map(int, input().split())
g = [[0 for i in range(n)] for j in range(n)]
G1 = [[] for i in range(n)]
G2 = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u][v] = 1
	g[v][u] = 1
	G1[u].append((1, v))
	G1[v].append((1, u))
(dist, prev) = dijkstra(G1, 0)
if dist[n - 1] != 10 ** 8:
	for i in range(n):
		for j in range(i + 1, n):
			if g[i][j] == 0:
				G2[i].append((1, j))
				G2[j].append((1, i))
	route = [False for i in range(n)]

	def dfs(count, v):
		route[count] = v
		if v == 0:
			return True
		dfs(count - 1, prev[v])
	dfs(dist[n - 1], n - 1)
	dist2 = dijkstra2(G2, 0, route)
	ans = max(dist[n - 1], dist2[n - 1])
else:
	ans = 10 ** 8
print(-1 if ans == 10 ** 8 else ans)


import math
g = []
ga = []

def bfs(gg):
	source = 0
	q = [source]
	d = {source: 0}
	while len(q) > 0:
		u = q.pop()
		for v in gg[u]:
			if v not in d or d[u] + 1 < d[v]:
				d[v] = d[u] + 1
				q.append(v)
	n = len(g) - 1
	if n not in d:
		return -1
	return d[n]

def main():
	(n, m) = map(int, input().split())
	global g
	for _ in range(n):
		g.append([])
		ga.append([])
	for _ in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		g[u].append(v)
		g[v].append(u)
	for i in range(n):
		for j in range(n):
			if i != j and j not in g[i]:
				ga[i].append(j)
	a1 = bfs(g)
	a2 = bfs(ga)
	if a1 < 0 or a2 < 0:
		print(-1)
	else:
		print(max(a1, a2))
main()


__author__ = 'Utena'
from collections import defaultdict
from heapq import *
M = 99999999

def dijkstra_raw(edges, from_node, to_node):
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
	(q, seen) = ([(0, from_node, ())], set())
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == to_node:
				return (cost, path)
			for (c, v2) in g.get(v1, ()):
				if v2 not in seen:
					heappush(q, (cost + c, v2, path))
	return (float('inf'), [])

def dijkstra(edges, from_node, to_node):
	len_shortest_path = -1
	ret_path = []
	(length, path_queue) = dijkstra_raw(edges, from_node, to_node)
	if len(path_queue) > 0:
		len_shortest_path = length
		left = path_queue[0]
		ret_path.append(left)
		right = path_queue[1]
		while len(right) > 0:
			left = right[0]
			ret_path.append(left)
			right = right[1]
		ret_path.reverse()
	return (len_shortest_path, ret_path)
(n, m) = map(int, input().split())
conn = [set() for i in range(n + 2)]
rail = []
road = []
for i in range(m):
	(a, b) = map(int, input().split())
	conn[a].add(b)
	conn[b].add(a)
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if j in conn[i]:
			rail.append((i, j, 1))
		else:
			road.append((i, j, 1))
a = dijkstra(rail, 1, n)[0]
b = dijkstra(road, 1, n)[0]
if a * b < 0:
	print(-1)
else:
	print(max(a, b))


(n, m) = map(int, input().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x][y] = graph[y][x] = 1
vis = [-1] * (n + 1)
vis[1] = 0
q = [1]
while q:
	x = q.pop(0)
	for y in range(1, n + 1):
		if graph[x][y] != graph[1][n] and vis[y] == -1:
			vis[y] = vis[x] + 1
			q.append(y)
print(vis[-1])


(n, m) = map(int, input().split())
A = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	A[u][v] = 1
	A[v][u] = 1
dist = [-1 for i in range(n)]
dist[0] = 0
Q = [0]
while len(Q) != 0:
	u = Q.pop(0)
	for v in range(n):
		if dist[v] == -1 and A[v][u] != A[0][n - 1]:
			dist[v] = dist[u] + 1
			Q.append(v)
print(dist[n - 1])


from collections import defaultdict

class graph_maker:

	def __init__(self, n):
		self.matrix = [[0 for _ in range(n)] for i in range(n)]

	def add_edge(self, u, v):
		self.matrix[u][v] = 1
		self.matrix[v][u] = 1

def dijkstra(n, graph):
	for i in range(n):
		graph[i][i] = -1
	path = defaultdict(int)
	infinite = float('inf')
	visited = [True] * n
	dist = [infinite] * (n - 1)
	dist = [0] + dist
	if graph[n - 1][0] == 1:
		while True:
			min_dist = min(dist)
			ind = dist.index(min_dist)
			if min_dist != infinite:
				if visited[ind]:
					visited[ind] = False
					for i in range(n):
						if visited[i]:
							if graph[ind][i] == 0:
								mi = min_dist + 1
								if mi < dist[i]:
									dist[i] = mi
									path[i] = mi
				dist[ind] = infinite
			else:
				break
		if visited[n - 1]:
			return -1
		return path[n - 1]
	else:
		while True:
			min_dist = min(dist)
			ind = dist.index(min_dist)
			if min_dist != infinite:
				if visited[ind]:
					visited[ind] = False
					for i in range(n):
						if visited[i]:
							if graph[ind][i] != 0:
								mi = min_dist + 1
								if mi < dist[i]:
									dist[i] = mi
									path[i] = mi
				dist[ind] = infinite
			else:
				break
		if visited[n - 1]:
			return -1
		return path[n - 1]
(n, m) = map(int, input().split())
graph = graph_maker(n)
for _ in range(m):
	(u, v) = map(int, input().split())
	graph.add_edge(u - 1, v - 1)
pa = dijkstra(n, graph.matrix)
print(pa)


(n, m) = list(map(int, input().split()))
a = [[] for i in range(n)]
r = False
for i in range(m):
	(x, y) = list(map(int, input().split()))
	if (x, y) == (1, n) or (x, y) == (n, 1):
		r = True
	a[x - 1].append(y - 1)
	a[y - 1].append(x - 1)
if r:
	for i in range(n):
		s = set(a[i])
		a[i] = [j for j in range(n) if i != j and (not j in s)]
q = [(0, 0)]
v = set([0])
l = 0
while l < len(q):
	(x, d) = q[l]
	l += 1
	for y in a[x]:
		if not y in v:
			if y == n - 1:
				print(d + 1)
				quit()
			q.append((y, d + 1))
			v.add(y)
print(-1)


def theTwoRoutes(cidadeX, cidadeY):
	cruzamento = [0] * (cidadeX + 1)
	for l in range(cidadeX + 1):
		cruzamento[l] = [1] * (cidadeX + 1)
	for i in range(cidadeY):
		(a, b) = map(int, input().split())
		cruzamento[a][b] = cruzamento[b][a] = 2
	x = 3 - cruzamento[1][cidadeX]
	veiculo = [0] * (cidadeX + 1)
	indice = 1
	d = [cidadeX + 1] * (cidadeX + 1)
	tempo = d[1] = 0
	while indice != cidadeX:
		veiculo[indice] = 1
		for j in range(1, cidadeX + 1):
			if veiculo[j] == 0 and cruzamento[indice][j] == x and (d[j] > d[indice] + 1):
				d[j] = d[indice] + 1
		menor = cidadeX + 1
		for j in range(1, cidadeX + 1):
			if veiculo[j] == 0 and d[j] < menor:
				menor = d[j]
				indice = j
		if menor == cidadeX + 1:
			tempo = -1
			break
		elif indice == cidadeX:
			tempo = d[cidadeX]
			break
	print(tempo)
(cidadeX, cidadeY) = map(int, input().split())
theTwoRoutes(cidadeX, cidadeY)


(number1, number2) = map(int, input().split())
aux = [0] * (number1 + 1)
for i in range(number1 + 1):
	aux[i] = [1] * (number1 + 1)
for i in range(number2):
	(x, y) = map(int, input().split())
	aux[x][y] = aux[y][x] = 2
(a, b, i) = (3 - aux[1][number1], [0] * (number1 + 1), 1)
d = [number1 + 1] * (number1 + 1)
result = d[1] = 0
while i != number1:
	b[i] = 1
	for j in range(1, number1 + 1):
		if b[j] == 0 and aux[i][j] == a and (d[j] > d[i] + 1):
			d[j] = d[i] + 1
	meu = number1 + 1
	for k in range(1, number1 + 1):
		if b[k] == 0 and d[k] < meu:
			meu = d[k]
			i = k
	if meu == number1 + 1:
		result = -1
		break
	elif i == number1:
		result = d[number1]
		break
print(result)


import heapq

def answer(n, g):
	path = [float('inf')] * (n + 1)
	vis = [0] * (n + 1)
	path[1] = 0
	q = [(0, 1)]
	while q:
		item = heapq.heappop(q)
		node = item[1]
		if vis[node] == 1:
			continue
		vis[node] = 1
		wt = item[0]
		for v in range(n + 1):
			if g[node][v] > 0 and vis[v] == 0:
				path[v] = min(path[v], wt + g[node][v])
				heapq.heappush(q, (path[v], v))
	return path[n]
(n, m) = map(int, input().split())
g = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	g[u][v] = 1
	g[v][u] = 1
if g[1][n] == 1:
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if g[i][j] == 1:
				g[i][j] = 0
			else:
				g[i][j] = 1
x = answer(n, g)
if x == float('inf'):
	print(-1)
else:
	print(max(1, x))


(cx, cy) = map(int, input().split())
cross = [0] * (cx + 1)
for l in range(cx + 1):
	cross[l] = [1] * (cx + 1)
for i in range(cy):
	(a, b) = map(int, input().split())
	cross[a][b] = cross[b][a] = 2
(x, v, i) = (3 - cross[1][cx], [0] * (cx + 1), 1)
d = [cx + 1] * (cx + 1)
t = d[1] = 0
while i != cx:
	v[i] = 1
	for j in range(1, cx + 1):
		if v[j] == 0 and cross[i][j] == x and (d[j] > d[i] + 1):
			d[j] = d[i] + 1
	m = cx + 1
	for j in range(1, cx + 1):
		if v[j] == 0 and d[j] < m:
			m = d[j]
			i = j
	if m == cx + 1:
		t = -1
		break
	elif i == cx:
		t = d[cx]
		break
print(t)


(n, m) = list(map(int, input().split()))
f = [set() for i in range(n)]
(g, h) = ([0] + (n - 1) * [10000], [0] + (n - 1) * [10000])
for i in range(m):
	(u, v) = list(map(int, input().split()))
	f[u - 1].add(v - 1)
	f[v - 1].add(u - 1)
p = {i for i in range(1, n)}

def findrailway(t):
	if t == 0:
		for c in f[t]:
			g[c] = g[t] + 1
		for c in f[t]:
			findrailway(c)
	if t != n - 1:
		pp = set()
		for c in f[t] - f[0]:
			if g[c] != min(g[c], g[t] + 1):
				g[c] = g[t] + 1
				pp.add(c)
		for c in pp:
			findrailway(c)

def findbusway(t):
	if t == 0:
		for c in p - f[t]:
			h[c] = h[t] + 1
		for c in p - f[t]:
			findbusway(c)
	if t != n - 1:
		pp = set()
		for c in p - f[t] - (p - f[0]):
			if h[c] != min(h[c], h[t] + 1):
				h[c] = h[t] + 1
				pp.add(c)
		for c in pp:
			findbusway(c)
findrailway(0)
findbusway(0)
print(max(h[n - 1], g[n - 1]) if h[n - 1] != g[n - 1] and h[n - 1] < 10000 and (g[n - 1] < 10000) else -1)


(n, k) = map(int, input().split())
vt = [[] for i in range(n + 1)]
vb = [[] for i in range(n + 1)]
queue = []
visit = [0 for i in range(n + 1)]
s = set([i for i in range(1, n + 1)])
for i in range(k):
	(a, b) = map(int, input().split())
	vt[a].append(b)
	vt[b].append(a)
visit[1] = 1
queue = [1]
if vt[n].count(1):
	for i in range(n):
		vb[i] = list(s - set(vt[i]))
	h = 0
	t = 1
	while h != t:
		v = queue[h]
		h += 1
		for u in vb[v]:
			if not visit[u]:
				visit[u] = visit[v] + 1
				queue.append(u)
				t += 1
	print(visit[n] - 1)
else:
	h = 0
	t = 1
	while h != t:
		v = queue[h]
		h += 1
		for u in vt[v]:
			if not visit[u]:
				visit[u] = visit[v] + 1
				queue.append(u)
				t += 1
	print(visit[n] - 1)


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

def possible(n):
	vis = [0] * (n + 1)
	que = deque([(1, 0)])
	ans = 0
	while que:
		(z, dst) = que.popleft()
		if vis[z]:
			continue
		vis[z] = 1
		if z == n:
			ans = dst
			break
		for item in d[z]:
			if vis[item] == 0:
				que.append((item, dst + 1))
	return ans
d = [set([]) for _ in range(401)]

def main():
	(n, m) = map(int, input().split())
	for _ in range(m):
		(u, v) = map(int, input().split())
		d[u].add(v)
		d[v].add(u)
	if m == n * (n - 1) // 2:
		print(-1)
		exit()
	dst = possible(n)
	if dst == 0:
		print(-1)
		exit()
	for i in range(2, n):
		if i not in d[1] and i not in d[n]:
			print(max(2, dst))
			exit()
	dd = [[] for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if j not in d[i] and i != j:
				dd[i].append(j)
	vis = [0] * (n + 1)
	que = deque([(1, 0)])
	ans = 0
	while que:
		(z, dist) = que.popleft()
		if vis[z]:
			continue
		vis[z] = 1
		if z == n:
			ans = dist
			break
		for item in dd[z]:
			if vis[item] == 0:
				que.append((item, dist + 1))
	if ans == 0:
		print(-1)
		exit()
	else:
		print(max(ans, dst))
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()


from math import inf
from collections import Counter as cntr
(n, m) = map(int, input().split(' '))
road = [[1 for i in range(n)] for i in range(n)]
railway = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split(' '))
	u -= 1
	v -= 1
	road[u][v] = 0
	road[v][u] = 0
	railway[u][v] = 1
	railway[v][u] = 1

def bfs(graph, source, n):
	visited = [False for i in range(n)]
	d = [inf for i in range(n)]
	q = [source]
	visited[source] = True
	d[source] = 0
	while q:
		idx = q.pop(0)
		for i in range(n):
			if graph[idx][i] == 1 and visited[i] == False:
				visited[i] = True
				d[i] = d[idx] + 1
				q.append(i)
	return d
l1 = bfs(road, 0, n)
l2 = bfs(railway, 0, n)
ans = max(l1[-1], l2[-1])
print(-1) if ans == inf else print(ans)


from collections import deque
UNDEF = float('inf')
(nV, nE) = map(int, input().split())
g = [[] for _ in range(nV)]
for _ in range(nE):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	g[u].append(v)
	g[v].append(u)
g1 = [[] for _ in range(nV)]
for v in range(nV):
	for u in range(v + 1, nV):
		if u not in g[v]:
			g1[u].append(v)
			g1[v].append(u)

def bfs(g):
	q = deque([0])
	dist = [0] + [UNDEF] * (nV - 1)
	while q:
		v = q.pop()
		for to in g[v]:
			if dist[to] == UNDEF:
				dist[to] = dist[v] + 1
				q.appendleft(to)
	return dist[nV - 1]
dist = (bfs(g), bfs(g1))
print(-1 if UNDEF in dist else max(dist))


def main():
	(n, m) = map(int, input().split())
	vrtxs = [[False] * n for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		vrtxs[u][v] = vrtxs[v][u] = True
	if vrtxs[0][n - 1]:
		for (u, l) in enumerate(vrtxs):
			for (v, f) in enumerate(l):
				l[v] = not f
			l[u] = False
	(avail, nxt, t) = ([True] * n, [n - 1], 0)
	while nxt:
		(cur, nxt) = (nxt, [])
		t += 1
		for u in cur:
			for (v, f, a) in zip(range(n), vrtxs[u], avail):
				if f and a:
					if not v:
						print(t)
						return
					avail[v] = False
					nxt.append(v)
	print(-1)
main()


def fast_rail(n, graph):
	return 1 in graph and n in graph[1]

def main():
	(n, m) = map(int, input().split())
	graph = {}
	for _ in range(m):
		(u, v) = map(int, input().split())
		if u not in graph:
			graph[u] = [v]
		else:
			graph[u].append(v)
		if v not in graph:
			graph[v] = [u]
		else:
			graph[v].append(u)
	visited = {1: 0}
	unvisited = [1]
	if fast_rail(n, graph):
		while len(unvisited) > 0:
			node = unvisited.pop(0)
			moves = visited[node]
			for connection in range(1, n + 1):
				if node in graph and connection in graph[node]:
					continue
				if connection in visited:
					continue
				if connection == n:
					print(moves + 1)
					return
				unvisited.append(connection)
				visited[connection] = moves + 1
		print(-1)
	else:
		if 1 in graph:
			while len(unvisited) > 0:
				node = unvisited.pop(0)
				moves = visited[node]
				for connection in graph[node]:
					if connection in visited:
						continue
					if connection == n:
						print(moves + 1)
						return
					unvisited.append(connection)
					visited[connection] = moves + 1
		print(-1)
main()


from collections import deque
(n, m) = tuple(map(int, input().split()))
(li, s) = (deque([0]), set())
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	s.add((a, b))
	s.add((b, a))
reach = (0, n - 1) in s
d = [0]
d.extend([-1 for _ in range(n - 1)])
while li:
	a = li.popleft()
	for b in range(n):
		if not (reach and (a, b) in s) and (reach or (a, b) in s) and (d[b] == -1 or d[b] > d[a] + 1):
			d[b] = d[a] + 1
			li.append(b)
print(d[n - 1])


(n, m) = list(map(int, input().split()))
l = [[0] * n for i in range(n)]
for i in range(m):
	(x, y) = list(map(int, input().split()))
	l[x - 1][y - 1] = 1
	l[y - 1][x - 1] = 1
p = [-1] * n
p[0] = 0
q = [0]
while q:
	i = q.pop(0)
	for j in range(n):
		if l[i][j] != l[0][n - 1] and p[j] == -1:
			p[j] = p[i] + 1
			q.append(j)
print(p[n - 1])


(n, m) = map(int, input().split())
g_road = [[True for i in range(n)] for j in range(n)]
g_rail = [[False for i in range(n)] for j in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	g_rail[u - 1][v - 1] = g_rail[v - 1][u - 1] = True
	g_road[u - 1][v - 1] = g_road[v - 1][u - 1] = False
visit = [False] * (n + 1)
(start, goal) = (0, n - 1)
if g_rail[start][goal]:
	g = g_road
else:
	g = g_rail
visit[0] = True
queue = [(start, 0)]
tail = 0
while tail < len(queue):
	(u, steps) = queue[tail]
	tail += 1
	for v in range(n):
		if g[u][v] and (not visit[v]):
			if v == goal:
				print(steps + 1)
				import sys
				sys.exit()
			visit[v] = True
			queue.append((v, steps + 1))
print(-1)


from collections import deque

def min_route(n, edge_fn):
	t = 0
	s = {1}
	seen = set()
	unseen = set(range(1, n + 1))
	while s:
		seen |= s
		unseen -= s
		ns = set()
		for u in s:
			if u == n:
				return t
			ns |= {v for v in unseen if edge_fn(u, v)}
		t += 1
		s = ns

def time(n, r):

	def train(u, v):
		return (u, v) in r or (v, u) in r

	def road(u, v):
		return not train(u, v)
	tt = min_route(n, train)
	tb = min_route(n, road)
	if tt is not None and tb is not None:
		return max(tt, tb)

def pair(i):
	(u, v) = i
	return (u, v)
(n, m) = map(int, input().split())
r = {pair(map(int, input().split())) for _ in range(m)}
t = time(n, r)
print(-1 if t is None else t)


from collections import deque

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

def bfs(c):
	q = deque()
	q.append(1)
	vis[1] = 0
	while q:
		i = q.popleft()
		for j in range(1, n + 1):
			if graph[i][j] == c and vis[j] == -1:
				q.append(j)
				vis[j] = vis[i] + 1
	print(vis[n])
(n, m) = put()
graph = [[0] * (n + 1) for _ in range(n + 1)]
vis = [-1] * (n + 1)
for _ in range(m):
	(x, y) = put()
	graph[x][y] = 1
	graph[y][x] = 1
c = 1 - graph[1][n]
bfs(c)


(n, m) = map(int, input().split())
train = [[1e+200 for _ in range(n)] for i in range(n)]
oto = [[1 for _ in range(n)] for i in range(n)]
for i in range(n):
	oto[i][i] = 0
	train[i][i] = 0
for _ in range(m):
	(i, j) = map(int, input().split())
	(train[i - 1][j - 1], train[j - 1][i - 1]) = (1, 1)
	(oto[i - 1][j - 1], oto[j - 1][i - 1]) = (1e+200, 1e+200)
if oto[0][n - 1] == 1:
	for k in range(n):
		for i in range(n):
			for j in range(i, n):
				train[i][j] = min(train[min(i, k)][max(i, k)] + train[min(j, k)][max(j, k)], train[i][j])
else:
	for k in range(n):
		for i in range(n):
			for j in range(i, n):
				oto[i][j] = min(oto[min(i, k)][max(i, k)] + oto[min(j, k)][max(j, k)], oto[i][j])
e = max(train[0][n - 1], oto[0][n - 1])
print(e) if e < 1e+200 else print(-1)


from queue import Queue

def solve(net1, net2, n):
	res = [400 * 400] * n
	visited = [False] * n
	q = Queue(400 * 400)
	q.put((0, 0))
	visited[0] = True
	res[0] = 0
	while not q.empty():
		(town, t) = q.get()
		for next_town in net1[town]:
			if not visited[next_town]:
				res[next_town] = t + 1
				visited[next_town] = True
				q.put((next_town, t + 1))
	res2 = [400 * 400] * n
	visited = [False] * n
	q = Queue(400 * 400)
	q.put((0, 0))
	visited[0] = True
	res2[0] = 0
	while not q.empty():
		(town, t) = q.get()
		if res[town] != 400 * 400 and t > res[town]:
			continue
		for next_town in net2[town]:
			if next_town == n - 1:
				return max(t + 1, res[n - 1])
			if not visited[next_town]:
				if res[next_town] == t + 1:
					q.put((next_town, t + 3))
					res2[next_town] = t + 3
				else:
					q.put((next_town, t + 1))
					visited[next_town] = True
					res2[next_town] = t + 1
	return 400 * 400
(n, m) = [int(x) for x in input().split()]
roads = [set([x for x in range(n)]) for y in range(n)]
for u in range(n):
	roads[u].remove(u)
rails = [set() for x in range(n)]
for _ in range(m):
	(u, v) = [int(x) - 1 for x in input().split()]
	roads[u].remove(v)
	roads[v].remove(u)
	rails[u].add(v)
	rails[v].add(u)
res = min(solve(rails, roads, n), solve(roads, rails, n))
print(res if res != 400 * 400 else -1)


from collections import defaultdict
import heapq
(n, m) = map(int, input('').split())
rail_list = defaultdict(list)
for i in range(m):
	(start, end) = map(int, input('').split())
	rail_list[start].append(end)
	rail_list[end].append(start)

def dijkstra_on_road():
	dist_road = {i: float('inf') for i in range(1, n + 1)}
	towns = set(range(1, n + 1))
	H_road = [(0, 1)]
	while len(H_road) != 0:
		(curr_road_dist, curr_road_id) = heapq.heappop(H_road)
		if curr_road_dist <= dist_road[curr_road_id]:
			road_neighbours = towns - set(rail_list[curr_road_id] + [curr_road_id])
			for road_neigbour_id in road_neighbours:
				new_road_distance = curr_road_dist + 1
				if new_road_distance < dist_road[road_neigbour_id]:
					dist_road[road_neigbour_id] = new_road_distance
					heapq.heappush(H_road, (new_road_distance, road_neigbour_id))
	return dist_road[n]

def dijkstra_on_rail():
	dist_rail = {i: float('inf') for i in range(1, n + 1)}
	H_rail = [(0, 1)]
	while len(H_rail) != 0:
		(curr_rail_dist, curr_rail_id) = heapq.heappop(H_rail)
		if curr_rail_dist <= dist_rail[curr_rail_id]:
			for rail_neighbour_id in rail_list[curr_rail_id]:
				new_rail_distance = curr_rail_dist + 1
				if new_rail_distance < dist_rail[rail_neighbour_id]:
					dist_rail[rail_neighbour_id] = new_rail_distance
					heapq.heappush(H_rail, (new_rail_distance, rail_neighbour_id))
	return dist_rail[n]
if n in rail_list[1]:
	road_time = dijkstra_on_road()
	if road_time != float('inf'):
		print(road_time)
	else:
		print('-1')
else:
	rail_time = dijkstra_on_rail()
	if rail_time != float('inf'):
		print(rail_time)
	else:
		print('-1')


CONST_MAX = 999999999
adj_matrix = []
source_dist = []

def BFS(t):
	visited = []
	for i in range(500):
		source_dist.append(CONST_MAX)
		visited.append(False)
	queue = []
	queue.append(1)
	visited[1] = True
	source_dist[1] = 0
	while len(queue) > 0:
		current = queue[0]
		del queue[0]
		for i in range(1, n + 1):
			if t == True:
				if adj_matrix[current][i] == 1 and visited[i] == False:
					queue.append(i)
					visited[i] = True
					source_dist[i] = source_dist[current] + 1
					if i == n:
						return
			elif adj_matrix[current][i] == 0 and visited[i] == False:
				queue.append(i)
				visited[i] = True
				source_dist[i] = source_dist[current] + 1
				if i == n:
					return
(n, m) = map(int, input().split())
t = 0
b = 0
for i in range(500):
	adj_matrix.append([])
	for j in range(500):
		adj_matrix[i].append(0)
for i in range(m):
	(u, v) = map(int, input().split())
	adj_matrix[u][v] = 1
	adj_matrix[v][u] = 1
if adj_matrix[1][n] == 1:
	t = True
if t:
	BFS(False)
	b = source_dist[n]
else:
	BFS(True)
	t = source_dist[n]
if max(b, t) == CONST_MAX:
	print(-1)
else:
	print(max(b, t))


from collections import deque
(n, m) = map(int, input().split())
e = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	e[u][v] = 1
	e[v][u] = 1
vis = [0] * (n + 1)
vis[1] = 1
dis = [0] * (n + 1)
q = deque([1])
while q:
	cur = q.popleft()
	for to in filter(lambda x: e[cur][x], range(1, n + 1)):
		if not vis[to]:
			vis[to] = 1
			dis[to] = dis[cur] + 1
			q.append(to)
			if to == n:
				q.clear()
				break
d1 = dis[n]
vis = [0] * (n + 1)
vis[1] = 1
dis = [0] * (n + 1)
q = deque([1])
while q:
	cur = q.popleft()
	for to in filter(lambda x: not e[cur][x], range(1, n + 1)):
		if not vis[to] and to != cur:
			vis[to] = 1
			dis[to] = dis[cur] + 1
			q.append(to)
			if to == n:
				q.clear()
				break
d2 = dis[n]
if d1 == 0 or d2 == 0:
	print(-1)
else:
	print(max(d1, d2))


from queue import Queue
(n, m) = map(int, input().split())
maxn = 407
edges = [[False for j in range(maxn)] for i in range(maxn)]
for i in range(m):
	(u, v) = map(int, input().split())
	edges[u][v] = True
	edges[v][u] = True
if edges[1][n]:
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			edges[i][j] ^= 1
queue = Queue(0)
dist = [-1] * maxn
dist[1] = 0
queue.put(1)
while not queue.empty():
	u = queue.get()
	for i in range(1, n + 1):
		if edges[u][i] and dist[i] == -1:
			dist[i] = dist[u] + 1
			queue.put(i)
print(dist[n])


import sys
(n, m) = map(int, input().split())
railways = [[False] * n for _ in range(n)]
railways_list = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	railways[u][v] = railways[v][u] = True
	railways_list[u].append(v)
	railways_list[v].append(u)
if railways[0][n - 1]:
	for i in range(n):
		railways_list[i] = [j for j in range(n) if i != j and (not railways[i][j])]
		for j in range(n):
			railways[i][j] = not railways[i][j]
shortest = [n] * n
shortest[0] = 0
eunda = [0]
ita = set()
while eunda:
	eunda.sort(key=shortest.__getitem__)
	curr = eunda.pop(0)
	ita.add(curr)
	for eundum in railways_list[curr]:
		if eundum not in ita:
			if eundum not in eunda:
				eunda.append(eundum)
			shortest[eundum] = min(shortest[eundum], shortest[curr] + 1)
if shortest[n - 1] == n:
	print(-1)
else:
	print(shortest[n - 1])


(n, m) = map(int, input().split())
rails = [set() for u in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	rails[u].add(v)
	rails[v].add(u)
roads = [set() for u in range(n + 1)]
for u in range(1, n + 1):
	for v in range(u + 1, n + 1):
		if u not in rails[v]:
			roads[u].add(v)
			roads[v].add(u)

def bfs(n, adj):
	dist = [-1 for i in range(n + 1)]
	vis = [False for i in range(n + 1)]
	frontier = [1]
	dist[1] = 0
	ptr = 0
	while ptr < len(frontier):
		u = frontier[ptr]
		if u == n:
			return dist[u]
		if not vis[u]:
			vis[u] = True
			for v in adj[u]:
				if dist[v] == -1:
					dist[v] = dist[u] + 1
					frontier.append(v)
		ptr += 1
	return -1
(ans1, ans2) = (bfs(n, rails), bfs(n, roads))
if ans1 == -1 or ans2 == -1:
	print(-1)
else:
	print(max(ans1, ans2))


import sys

class BFSNode(object):

	def __init__(self, value, level):
		self.value = value
		self.level = level

def shortestPath(adjMatrix, N, value):
	queue = [0]
	marker = [-1] * N
	marker[0] = 0
	qIndex = 0
	while qIndex < len(queue):
		first = queue[qIndex]
		qIndex += 1
		for i in range(N):
			b = adjMatrix[first][i]
			if b == value and marker[i] == -1:
				marker[i] = marker[first] + 1
				queue.append(i)
	return marker[N - 1]

def printBFS(root, offset):
	print('-' * offset + str(root.value) + ' (' + str(root.level) + ')')
	for n in root.children:
		printBFS(n, offset + 1)
(n, e) = input().split()
(n, e) = (int(n), int(e))
adjMatrix = [[-1 for x in range(n)] for y in range(n)]
for j in range(e):
	(a, b) = input().split()
	(a, b) = (int(a) - 1, int(b) - 1)
	adjMatrix[a][b] = 1
	adjMatrix[b][a] = 1
for i in range(n):
	adjMatrix[i][i] = 0
if adjMatrix[0][n - 1] == 1:
	value = -1
else:
	value = 1
result = shortestPath(adjMatrix, n, value)
print(result)


import math
from collections import deque
d = {}
INF = 1000

def dijkstra(g):
	n = len(g)
	d = [INF] * n
	source = 0
	d[source] = 0
	used = [False] * n
	for _ in range(n):
		u = -1
		for v in range(n):
			if not used[v] and (u == -1 or d[v] < d[u]):
				u = v
		used[u] = True
		for v in g[u]:
			d[v] = min(d[v], d[u] + 1)
	if d[n - 1] == INF:
		return -1
	return d[n - 1]

def main():
	(n, m) = map(int, input().split())
	g = []
	gg = []
	for _ in range(n):
		g.append([])
		gg.append([])
	for _ in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		g[u].append(v)
		g[v].append(u)
	for i in range(n):
		for j in range(n):
			if i != j and j not in g[i]:
				gg[i].append(j)
	a1 = dijkstra(g)
	a2 = dijkstra(gg)
	if a1 < 0 or a2 < 0:
		print(-1)
	else:
		print(max(a1, a2))
main()


(n, m) = map(int, input().split())
d = [[0 for i in range(n)] for i in range(n)]
w = [[10 * n for i in range(n)] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	d[a][b] = 1
	d[b][a] = 1
if d[0][n - 1] == 1:
	for i in range(n):
		for j in range(n):
			d[i][j] = (d[i][j] + 1) % 2
w[0][0] = 0
g = 1
sosed = set()
sosed.add(0)
while len(sosed) > 0:
	sosed2 = set()
	for j in sosed:
		for i in range(n):
			if d[j][i] == 1:
				if w[j][i] > g:
					w[j][i] = g
					w[i][j] = g
					sosed2.add(i)
	sosed = sosed2.copy()
	g += 1
ans = min(w[n - 1])
if ans >= 2 * n:
	print(-1)
else:
	print(ans)


n = m = None
distance = None

def entrypoint():
	global n, m, distance
	(n, m) = map(int, input().split())
	distance = [[1 for col in range(n + 1)] for row in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		distance[a][b] = 2
		distance[b][a] = 2

def process():
	x = 3 - distance[1][n]
	(res, i) = (0, 1)
	vis = [0] * (n + 1)
	d = [n + 1] * (n + 1)
	d[1] = 0
	while i != n:
		vis[i] = 1
		for j in range(1, n + 1):
			if vis[j] == 0 and distance[i][j] == x and (d[j] > d[i] + 1):
				d[j] = d[i] + 1
		mine = n + 1
		for j in range(1, n + 1):
			if vis[j] == 0 and d[j] < mine:
				mine = d[j]
				i = j
		if mine == n + 1:
			res = -1
			break
		if i == n:
			res = d[n]
			break
	return res

def main():
	entrypoint()
	print(process())
main()


from _collections import deque
(n, m) = map(int, input().split())
gr = [[] for _ in range(n)]
st = set()
mt = [[0] * n for _ in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	mt[u][v] = 1
	mt[v][u] = 1
tmp = 1
if mt[0][-1]:
	tmp = 0
for i in range(n):
	for j in range(n):
		if mt[i][j] == tmp:
			gr[i].append(j)
depth = [-1] * n
q = deque()
depth[0] = 0
q.append(0)
while q:
	v = q.popleft()
	for u in gr[v]:
		if depth[u] == -1:
			depth[u] = depth[v] + 1
			q.append(u)
if depth[-1] == -1:
	print(-1)
else:
	print(depth[-1])


from __future__ import print_function
import sys
from collections import *
from heapq import *
from functools import *
import re
from itertools import *
INF = float('inf')
NINF = float('-inf')
try:
	input = raw_input
except:
	pass

def read_string():
	return input()

def read_string_line():
	return [x for x in input().split(' ')]

def read_int_line():
	return [int(x) for x in input().split(' ')]

def read_int():
	return int(input())
(n, m) = read_int_line()
a = [[0] * n for _ in range(n)]
for _ in range(m):
	(frm, to) = read_int_line()
	frm -= 1
	to -= 1
	a[frm][to] = a[to][frm] = 1

def calc():
	dist = [-1] * n
	dist[0] = 0
	q = deque([0])
	while q:
		cur = q.popleft()
		for nxt in range(n):
			if a[cur][nxt] != a[0][n - 1] and dist[nxt] == -1:
				dist[nxt] = dist[cur] + 1
				q.append(nxt)
	return dist[-1]
print('%d' % calc())


class CodeforcesTask601ASolution:

	def __init__(self):
		self.result = ''
		self.n_m = []
		self.railways = []

	def read_input(self):
		self.n_m = [int(x) for x in input().split(' ')]
		for x in range(self.n_m[1]):
			self.railways.append([int(y) for y in input().split(' ')])

	def process_task(self):
		training = True
		for railway in self.railways:
			if railway == [self.n_m[0], 1] or railway == [1, self.n_m[0]]:
				training = False
				break
		visits = {}
		to_visit = [(1, 0)]
		if training:
			graph = [[] for x in range(self.n_m[0])]
			for railway in self.railways:
				graph[railway[0] - 1].append(railway[1])
				graph[railway[1] - 1].append(railway[0])
		else:
			graph = [[] for x in range(self.n_m[0])]
			for railway in self.railways:
				graph[railway[0] - 1].append(railway[1])
				graph[railway[1] - 1].append(railway[0])
			for x in range(self.n_m[0]):
				graph[x] = list(set([y for y in range(1, self.n_m[0] + 1)]).difference(set(graph[x])))
		while to_visit:
			visiting = to_visit.pop(-1)
			if visiting[0] in visits:
				if visiting[1] < visits[visiting[0]]:
					visits[visiting[0]] = visiting[1]
					for adj in graph[visiting[0] - 1]:
						to_visit.append((adj, visiting[1] + 1))
			else:
				visits[visiting[0]] = visiting[1]
				for adj in graph[visiting[0] - 1]:
					to_visit.append((adj, visiting[1] + 1))
		if self.n_m[0] in visits:
			self.result = str(visits[self.n_m[0]])
		else:
			self.result = '-1'

	def get_result(self):
		return self.result
Solution = CodeforcesTask601ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())