Read problems statements in Mandarin Chinese  and Russian. 

Sometimes mysteries happen. Chef found a directed graph with N vertices and M edges in his kitchen! 
The evening was boring and chef has nothing else to do, so to entertain himself, Chef thought about a question "What is the minimum number of edges he needs to reverse in order to have at least one path from vertex 1 to vertex N, where the vertices are numbered from 1 to N.

------ Input ------ 

Each test file contains only one test case.
The first line of the input contains two space separated integers N and M, denoting the number of vertices and the number of edges in the graph respectively. The i^{th} line of the next M lines contains two space separated integers X_{i} and Y_{i}, denoting that the i^{th} edge connects vertices from X_{i} to Y_{i}.

------ Output ------ 

In a single line, print the minimum number of edges we need to revert. If there is no way of having at least one path from 1 to N, print -1.

------ Constraints ------ 

$1 ≤ N, M ≤ 100000 = 10^{5}$
$1 ≤ X_{i}, Y_{i} ≤ N$
$There can be multiple edges connecting the same pair of vertices, There can be self loops too i.e.  X_{i} = Y_{i} $

----- Sample Input 1 ------ 
7 7
1 2 
3 2
3 4
7 4
6 2
5 6
7 5
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
We can consider two paths from 1 to 7:
1-2-3-4-7 
1-2-6-5-7 
In the first one we need to revert edges (3-2), (7-4). In the second one - (6-2), (5-6), (7-5). So the answer is  min(2, 3) = 2.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Directed graphs

Shortest paths

Data structures
Skill types: Data structures

Starter code:

Solutions:
from heapq import *
(N, M) = map(int, input().split())
graph = dict({op: [] for op in range(1, N + 1)})
for _ in range(M):
	(u, v) = map(int, input().split())
	graph[u].append([v, 0])
	graph[v].append([u, 1])
queue = [[0, 1]]
heapify(queue)
shor_dis = [-1 for _ in range(N)]
vis_arr = [False for _ in range(N)]
shor_dis[0] = 0
if_break = False
while queue:
	(dis, node) = heappop(queue)
	vis_arr[node - 1] = True
	if node == N:
		print(shor_dis[N - 1])
		if_break = True
		break
	else:
		for i in range(len(graph[node])):
			(child, weight) = (graph[node][i][0], graph[node][i][1])
			if not vis_arr[child - 1] and (shor_dis[child - 1] == -1 or shor_dis[child - 1] > shor_dis[node - 1] + weight):
				shor_dis[child - 1] = shor_dis[node - 1] + weight
				heappush(queue, [shor_dis[child - 1], child])
if not if_break:
	print(-1)


from collections import defaultdict, deque
from heapq import *
(n, m) = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].append([b, 0])
	graph[b].append([a, 1])
s = 1
e = n
weights = [[0, 1]]
heapify(weights)
found = False
vis = set()
while weights:
	(curWt, newNode) = heappop(weights)
	if newNode in vis:
		continue
	if newNode == e:
		found = True
		print(curWt)
		break
	vis.add(newNode)
	for node in graph[newNode]:
		(nbr, w) = node
		if nbr not in vis:
			heappush(weights, [curWt + w, nbr])
if not found:
	print(-1)


from heapq import heappush, heappop

def reverseEdges(n, start, end, edgeList):
	graph = {}
	for i in edgeList:
		if i[0] not in graph:
			graph[i[0]] = []
		if i[1] not in graph:
			graph[i[1]] = []
		graph[i[0]].append([i[1], 0])
		graph[i[1]].append([i[0], 1])
	visited = [0] * (n + 1)
	heap = [[0, start]]
	ans = float('inf')
	while heap:
		x = heappop(heap)
		if visited[x[1]]:
			continue
		if x[1] == end:
			return x[0]
		visited[x[1]] = 1
		for i in graph[x[1]]:
			heappush(heap, [x[0] + i[1], i[0]])
	return -1
(n, m) = list(map(int, input().split()))
edges = []
for i in range(m):
	edge = list(map(int, input().split()))
	edges.append(edge)
print(reverseEdges(n, 1, n, edges))


import queue
import sys

def fun(d, v, e):
	ListOfQueues = [queue.Queue() for i in range(2)]
	ListOfQueues[0].put([1, 0])
	visited = set()
	x = 0
	while ListOfQueues[0].qsize() > 0 or ListOfQueues[1].qsize() > 0:
		while ListOfQueues[0].qsize() > 0:
			rem = ListOfQueues[0].get()
			if rem[0] in visited:
				continue
			visited.add(rem[0])
			if rem[0] == v:
				return rem[1]
			for nbr in d[rem[0]]:
				dest = nbr[0]
				cost = nbr[1]
				if dest not in visited:
					if cost == 0:
						ListOfQueues[0].put([dest, rem[1]])
					else:
						ListOfQueues[1].put([dest, rem[1] + 1])
		ListOfQueues = ListOfQueues[::-1]
		x += 1
	return -1
(v, e) = map(int, input().split())
d = {}
for i in range(e):
	(frm, to) = map(int, input().split())
	if frm in d:
		d[frm].append([to, 0])
	else:
		d[frm] = [[to, 0]]
	if to in d:
		d[to].append([frm, 1])
	else:
		d[to] = [[frm, 1]]
print(fun(d, v, e))


import heapq
(n, m) = list(map(int, input().split()))
graph = {}
n = n + 1
for i in range(n):
	graph[i] = []

def add_edge(u, v):
	graph[u].append((v, 0))
	graph[v].append((u, 1))
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	add_edge(u, v)

def shortestPath(graph, src, n, dest):
	pq = []
	heapq.heappush(pq, (0, src))
	dist = [float('inf')] * n
	dist[src] = 0
	while pq:
		(cost, u) = heapq.heappop(pq)
		if u == dest:
			return cost
		for adj in graph[u]:
			v = adj[0]
			weight = adj[1]
			if dist[v] > dist[u] + weight:
				dist[v] = dist[u] + weight
				heapq.heappush(pq, (dist[v], v))
	if dist[dest] == float('inf'):
		return -1
print(shortestPath(graph, 1, n, n - 1))


import heapq
(n, m) = map(int, input().split())
dict = {}
for i in range(m):
	(x, y) = map(int, input().split())
	try:
		dict[x].append((y, 0))
	except:
		dict[x] = [(y, 0)]
	try:
		dict[y].append((x, 1))
	except:
		dict[y] = [(x, 1)]
visited = [0 for i in range(n + 1)]
dist = [100000000 for i in range(n + 1)]
qu = []
heapq.heappush(qu, (0, 1))
dist[1] = 0
flag = False
while len(qu) > 0:
	node = heapq.heappop(qu)
	if visited[node[1]] == 1:
		continue
	visited[node[1]] = 1
	if node[1] == n:
		flag = True
		print(node[0])
		break
	for curr in dict[node[1]]:
		if curr[1] + node[0] < dist[curr[0]]:
			dist[curr[0]] = curr[1] + node[0]
			heapq.heappush(qu, (dist[curr[0]], curr[0]))
if flag == False:
	print(-1)


import heapq
(n, m) = input().split()
(n, m) = (int(n), int(m))
(s, d) = (1, n)
graph = {}
for i in range(m):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	if a not in graph:
		graph[a] = []
	if b not in graph:
		graph[b] = []
	graph[a].append((b, 0))
	graph[b].append((a, 1))
heap = [(0, s)]
visited = set()
flag = True
while heap:
	(cur_price, cur_node) = heapq.heappop(heap)
	if cur_node in visited:
		continue
	if cur_node == d:
		flag = False
		print(cur_price)
		break
	visited.add(cur_node)
	for (padosi, padosi_price) in graph[cur_node]:
		if padosi not in visited:
			heapq.heappush(heap, (cur_price + padosi_price, padosi))
if flag:
	print(-1)


from collections import defaultdict
import heapq
(v, e) = map(int, input().split())
g = defaultdict(list)
no_cost = defaultdict(int)
for _ in range(e):
	(x, y) = map(int, input().split())
	g[x - 1].append(y - 1)
	g[y - 1].append(x - 1)
	no_cost[x - 1, y - 1] = 1
q = [[0, 0]]
visited = [False] * v
while q:
	(cost, t) = heapq.heappop(q)
	if t == v - 1:
		print(cost)
		break
	if not visited[t]:
		visited[t] = True
		for i in g[t]:
			heapq.heappush(q, [cost + (0 if no_cost[t, i] else 1), i])
else:
	print(-1)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, m) = mp()
d = {i: [] for i in range(1, n + 1)}
for i in range(m):
	(a, b) = mp()
	d[a].append([b, 0])
	d[b].append([a, 1])
q = deque()
q.append([1, 0])
dist = [INF for i in range(n + 1)]
dist[1] = 0
while q:
	(x, y) = q.popleft()
	for i in d[x]:
		(node, distance) = i
		if y + distance < dist[node]:
			if distance == 0:
				q.appendleft([node, y])
				dist[node] = y
			else:
				q.append([node, y + 1])
				dist[node] = y + 1
pr(dist[n] if dist[n] != INF else -1)


import sys
(n, m) = map(int, input().split())
level = [10000000000.0 for i in range(n + 100)]
graph = [[] for i in range(n + 100)]

def create_graph():
	for i in range(m):
		(x, y) = map(int, input().split())
		if x == y:
			continue
		graph[x].append([y, 0])
		graph[y].append([x, 1])

def bfs(v=1):
	q = []
	q.append(v)
	level[1] = 0
	while len(q) != 0:
		cur_v = q[0]
		q.pop(0)
		for child in graph[cur_v]:
			c_v = child[0]
			wt = child[1]
			if level[cur_v] + wt < level[c_v]:
				if wt == 0:
					q.insert(0, c_v)
				else:
					q.append(c_v)
				level[c_v] = level[cur_v] + wt
	if level[n] == 10000000000.0:
		return -1
	return level[n]
create_graph()
print(bfs())


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(v1, v2) = [int(x) - 1 for x in input().split()]
	g[v1].append((v2, 0))
	g[v2].append((v1, 1))
d = [n] * n
q = deque([0])
d[0] = 0
while q:
	v = q.popleft()
	if v == n - 1:
		break
	for (to, cost) in g[v]:
		if d[to] > d[v] + cost:
			d[to] = d[v] + cost
			if cost == 0:
				q.appendleft(to)
			else:
				q.append(to)
print(-1 if d[n - 1] == n else d[n - 1])


from heapq import heapify, heappop, heappush

def bsf(source, dic, dist, n):
	dist[source] = 0
	vis = [False] * (n + 1)
	Q = [(dist[source], source)]
	while Q:
		(lent, ver) = heappop(Q)
		if ver == n:
			break
		if vis[ver]:
			continue
		else:
			vis[ver] = True
		for i in dic[ver]:
			if not vis[i]:
				dist[i] = min(dist[i], dic[ver][i] + dist[ver])
				heappush(Q, (dist[i], i))
	return dist[n]
from collections import defaultdict
(n, m) = map(int, input().split())
dist = [float('inf')] * (n + 1)
dic = defaultdict(lambda : defaultdict(lambda : float('inf')))
for i in range(m):
	(a, b) = map(int, input().split())
	dic[a][b] = min(dic[a][b], 0)
	dic[b][a] = min(dic[b][a], 1)
tot = bsf(1, dic, dist, n)
if tot == float('inf'):
	print(-1)
else:
	print(tot)


from queue import PriorityQueue

def dijkstra(G, src, des):
	dist = [1 << 28] * len(G)
	Q = PriorityQueue()
	dist[src] = 0
	Q.put((0, src))
	while Q.empty() == False:
		(cost, u) = Q.get()
		if u == des:
			return dist[des]
		l = len(G[u])
		for i in range(0, l):
			(v, Cost) = G[u][i]
			if dist[v] > cost + Cost:
				dist[v] = cost + Cost
				Q.put((dist[v], v))
	return -1
(N, M) = map(int, input().split())
Graph = [[] for i in range(N + 1)]
for i in range(0, M):
	(u, v) = map(int, input().split())
	Graph[u].append((v, 0))
	Graph[v].append((u, 1))
print(dijkstra(Graph, 1, N))


import io, os, time
from sys import stdin, stdout
from collections import defaultdict
from heapq import heappush as push, heappop as pop

def take_input():
	s = stdin.readline()
	return s

def display_arr(arr):
	stdout.write(' '.join(map(str, arr)) + '\n')

def display_num(num):
	stdout.write(str(num) + '\n')

def solve():
	dis = [float('inf')] * (n + 1)
	vis = [0] * (n + 1)
	dis[1] = 0
	heap = [(0, 1)]
	while heap:
		(distance, node) = pop(heap)
		if node == n:
			return distance
		vis[node] = 1
		for (adj, wt) in graph[node]:
			if vis[adj] == 0 and dis[adj] > distance + wt:
				dis[adj] = distance + wt
				push(heap, (distance + wt, adj))
	return dis[-1] if dis[-1] != float('inf') else -1
(n, m) = map(int, take_input().split())
graph = defaultdict(list)
for i in range(m):
	(u, v) = map(int, take_input().split())
	graph[u].append((v, 0))
	graph[v].append((u, 1))
print(solve())


from heapq import *
(n, m) = map(int, input().split())
adj = [[] for i in range(n)]
heap = []
for i in range(m):
	(x, y) = map(int, input().split())
	if x != y:
		adj[x - 1].append((y - 1, 0))
		adj[y - 1].append((x - 1, 1))
cost = [10 ** 9] * n
cost[0] = 0
for i in adj[0]:
	heap.append((i[1], i[0]))
	cost[i[0]] = i[1]
vis = [0] * n
vis[0] = 1
heapify(heap)
done = set()
while heap:
	node = heappop(heap)
	if node in done:
		continue
	done.add(node)
	if node[1] == n - 1:
		break
	for (i, co) in adj[node[1]]:
		vis[i] = 1
		if cost[i] > node[0] + co:
			cost[i] = node[0] + co
			heappush(heap, (cost[i], i))
if cost[n - 1] == 10 ** 9:
	print(-1)
else:
	print(cost[n - 1])


try:
	from collections import deque
	from sys import stdin
	import numpy as np
	(n, m) = map(int, input().split())
	Adj = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, stdin.readline().split())
		Adj[a].append([b, 0])
		Adj[b].append([a, 1])
	q = deque([1])
	d = np.ones(n + 1, dtype=np.uint32) * 10 ** 6
	d[1] = 0
	while q:
		q1 = q.popleft()
		for (v, w) in Adj[q1]:
			if d[v] > d[q1] + w:
				if w == 1:
					q.append(v)
				else:
					q.appendleft(v)
				d[v] = d[q1] + w
	dist = d[-1]
	if dist == 1000000:
		print(-1)
	else:
		print(dist)
except:
	pass


from collections import defaultdict
d = defaultdict(list)
(n, m) = map(int, input().split())
for i in range(m):
	(a, b) = map(int, input().split())
	a = a - 1
	b = b - 1
	d[a].append([b, 0])
	d[b].append([a, 1])
import heapq
l = []
dist = [10 ** 9] * n
dist[0] = 0
for i in d[0]:
	l.append([i[0], i[1]])
	dist[i[0]] = i[1]
heapq.heapify(l)
vis = [0] * n
while l:
	t = heapq.heappop(l)
	weight = t[1]
	elem = t[0]
	for x in d[elem]:
		vis[x[0]] = 1
		if x[1] + weight < dist[x[0]]:
			dist[x[0]] = x[1] + weight
			heapq.heappush(l, [x[0], dist[x[0]]])
print(dist[n - 1] if dist[n - 1] != 10 ** 9 else -1)


(N, M) = map(int, input().split())
adj = [0]
vis = [0]
for i in range(N):
	adj.append([])
	vis.append(0)
for i in range(M):
	(x, y) = map(int, input().split())
	adj[x].append([y, 0])
	adj[y].append([x, 1])
spt = []
dist = [0]
for i in range(N):
	if i == 0:
		dist.append(0)
	else:
		dist.append(10 ** 5)
q = [1]
mindist = 10 ** 5
(L1, L2) = (0, 1)
ans = -1
while L1 < N:
	mindist = 10 ** 5
	index = -1
	for i in range(L2):
		if dist[q[i]] < mindist:
			mindist = dist[q[i]]
			index = i
	if len(q) == 0:
		break
	node = q.pop(index)
	if node == N:
		ans = dist[N]
		break
	spt.append(node)
	vis[node] = 2
	L1 += 1
	L2 -= 1
	for i in adj[node]:
		if dist[node] + i[1] < dist[i[0]]:
			dist[i[0]] = dist[node] + i[1]
		if vis[i[0]] == 0:
			vis[i[0]] = 1
			q.append(i[0])
			L2 += 1
print(ans)


import sys
from collections import defaultdict
from collections import deque

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append((v, 0))
		self.graph[v].append((u, 1))

	def ZeroOne(self, source):
		dq = deque()
		dist = [sys.maxsize for i in range(self.V + 1)]
		dist[1] = 0
		dq.append((source, 0))
		while dq:
			(node, d) = dq.popleft()
			for (v, w) in self.graph[node]:
				if dist[v] > w + d:
					dist[v] = w + d
					if w == 1:
						dq.append((v, dist[v]))
					else:
						dq.appendleft((v, dist[v]))
		return dist[self.V]
(n, m) = map(int, input().split())
g = Graph(n)
for _ in range(m):
	(u, v) = map(int, input().split())
	g.addEdge(u, v)
ans = g.ZeroOne(1)
if ans == sys.maxsize:
	print(-1)
else:
	print(ans)


class GraphNode:

	def __init__(self, nodeB, weight):
		self.node = nodeB
		self.weight = weight

def bfs01(graph, numOfNodes):
	distance = [sys.maxsize for i in range(numOfNodes + 1)]
	distance[1] = 0
	visited = [False for i in range(numOfNodes + 1)]
	visited[1] = True
	heap = deque()
	heap.appendleft((0, 1))
	while len(heap) != 0:
		(dist, node) = heap.popleft()
		visited[node] = True
		for child in graph[node]:
			if not visited[child.node]:
				if distance[child.node] > dist + child.weight:
					distance[child.node] = dist + child.weight
					if child.weight == 0:
						heap.appendleft((distance[child.node], child.node))
					else:
						heap.append((distance[child.node], child.node))
	return distance[-1] if distance[-1] != sys.maxsize else -1

def code():
	(n, m) = [int(i) for i in input().split()]
	graph = {}
	for _ in range(m):
		(nodeA, nodeB) = [int(i) for i in input().split()]
		if nodeA not in graph:
			graph[nodeA] = []
		nodeAObj = GraphNode(nodeB, 0)
		graph[nodeA].append(nodeAObj)
		if nodeB not in graph:
			graph[nodeB] = []
		nodeBObj = GraphNode(nodeA, 1)
		graph[nodeB].append(nodeBObj)
	print(bfs01(graph, n))
from collections import deque
import sys
import heapq
sys.setrecursionlimit(10 ** 6)
code()


import heapq, sys

def solution(points, vertices, edges):
	adj = {i: [] for i in range(1, vertices + 1)}
	for i in range(edges):
		(x, y) = points[i]
		adj[x].append([0, y])
		adj[y].append([1, x])
	(pq, dist) = ([], [sys.maxsize] * (vertices + 1))
	heapq.heapify(pq)
	heapq.heappush(pq, [0, 1])
	dist[0] = 0
	dist[1] = 0
	while pq:
		(dista, u) = heapq.heappop(pq)
		for val in adj[u]:
			(weight, v) = val
			if dist[v] > dist[u] + weight:
				dist[v] = dist[u] + weight
				heapq.heappush(pq, [-weight, v])
	if dist[vertices] >= sys.maxsize:
		print('-1')
	else:
		print(dist[vertices])
(vertices, edges) = input().split()
(vertices, edges) = (int(vertices), int(edges))
points = [[]] * edges
for i in range(edges):
	(x, y) = input().split()
	points[i] = [int(x), int(y)]
solution(points, vertices, edges)


import heapq
(n, m) = map(int, input().split())
hash = {}
for i in range(n):
	hash[i + 1] = []
for i in range(m):
	(a, b) = map(int, input().split())
	try:
		hash[b]
	except:
		hash[b] = [[1, a]]
	else:
		hash[b].append([1, a])
	try:
		hash[a]
	except:
		hash[a] = [[0, b]]
	else:
		hash[a].append([0, b])
hash_ha = {}
for i in range(n):
	hash_ha[i + 1] = 10 ** 18
hash_ha[1] = 0
hash_bool = {}
for i in range(n):
	hash_bool[i + 1] = False

def bfs():
	queue = [1]
	hash_bool[1] = True
	while queue != []:
		z = queue.pop(0)
		for i in hash[z]:
			if hash_bool[i[1]] == False:
				hash_bool[i[1]] = True
				queue.append(i[1])
	return hash_bool
hash_bool = bfs()

def dijskstras():
	l = [[0, 1]]
	heapq.heapify(l)
	while l != []:
		z = heapq.heappop(l)
		for i in hash[z[1]]:
			if z[0] + i[0] < hash_ha[i[1]]:
				hash_ha[i[1]] = z[0] + i[0]
				heapq.heappush(l, [hash_ha[i[1]], i[1]])
	return hash_ha
if hash_bool[n] == False:
	print(-1)
else:
	z = dijskstras()
	print(z[n])


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
from collections import deque
tc = 1
for _ in range(tc):
	(n, m) = inp()
	g = [set() for i in range(n + 1)]
	for ind in range(m):
		(i, j) = inp()
		g[i].add((j, 0))
		g[i].discard((j, 1))
		if (i, 0) not in g[j]:
			g[j].add((i, 1))
	ans = INF
	weight = [INF] * (n + 1)
	weight[1] = 0
	q = deque([1])
	vis = [False] * (n + 1)
	while q:
		node = q.popleft()
		if vis[node] == True:
			continue
		vis[node] = True
		for (edge, wt) in g[node]:
			new_dist = weight[node] + wt
			if new_dist < weight[edge]:
				if wt == 1:
					q.append(edge)
				else:
					q.appendleft(edge)
				weight[edge] = new_dist
	print(-1 if weight[n] == INF else weight[n])


from heapq import heapify, heappush, heappop

def dij(ed, hp, d):
	while len(hp) != 0:
		val = heappop(hp)
		for (key, dis) in ed[val[1]]:
			if val[0] + dis < d[key]:
				d[key] = val[0] + dis
				heappush(hp, (val[0] + dis, key))
(n, m) = [int(a) for a in input().split()]
ed = []
for l in range(n + 1):
	ed.append([])
for _ in range(m):
	(u, v) = [int(a) for a in input().split()]
	if len(ed[u]) == 0:
		ed[u] = []
	ed[u].append([v, 0])
	if len(ed[v]) == 0:
		ed[v] = []
	ed[v].append([u, 1])
d = []
for l in range(n + 1):
	d.append(float('inf'))
d[1] = 0
hp = []
heapify(hp)
heappush(hp, (0, 1))
dij(ed, hp, d)
if d[n] == float('inf'):
	print(-1)
else:
	print(d[n])


from heapq import *
import math
(n, m) = map(int, input().split())
g = {}
for i in range(m):
	(a, b) = map(int, input().split())
	if a not in g:
		g[a] = []
		g[a].append([0, b])
	else:
		g[a].append([0, b])
	if b not in g:
		g[b] = []
		g[b].append([1, a])
	else:
		g[b].append([1, a])
vis = [0] * (n + 1)
dis = [math.inf] * (n + 1)
h = []
dis[1] = 0
heappush(h, [0, 1])
f_1 = 0
while len(h) > 0:
	t_1 = heappop(h)
	if vis[t_1[1]] == 1:
		continue
	vis[t_1[1]] = 1
	if t_1[1] == n:
		f_1 = 1
		print(t_1[0])
		break
	for i in g[t_1[1]]:
		if i[0] + t_1[0] < dis[i[1]]:
			dis[i[1]] = i[0] + t_1[0]
			heappush(h, [dis[i[1]], i[1]])
if f_1 == 0:
	print(-1)


import math
import os
import queue
from collections import namedtuple
Edge = namedtuple('Edge', ['vertex', 'weight'])

class Graph(object):

	def __init__(self, vertex_count):
		self.vertex_count = vertex_count
		self.adjacency_list = [[] for _ in range(vertex_count)]

	def add_edge(self, source, dest, weight):
		assert source < self.vertex_count
		assert dest < self.vertex_count
		self.adjacency_list[source].append(Edge(dest, weight))
		self.adjacency_list[dest].append(Edge(source, 1))

	def get_edge(self, vertex):
		for e in self.adjacency_list[vertex]:
			yield e

	def get_vertex(self):
		for v in range(self.vertex_count):
			yield v

def dijkstra(graph, source, dest):
	q = queue.PriorityQueue()
	parents = []
	distances = []
	start_weight = float('inf')
	for i in graph.get_vertex():
		weight = start_weight
		if source == i:
			weight = 0
		distances.append(weight)
		parents.append(None)
	q.put([0, source])
	while not q.empty():
		v_tuple = q.get()
		v = v_tuple[1]
		for e in graph.get_edge(v):
			candidate_distance = distances[v] + e.weight
			if distances[e.vertex] > candidate_distance:
				distances[e.vertex] = candidate_distance
				parents[e.vertex] = v
				if candidate_distance < -1000:
					raise Exception('Negative cycle detected')
				q.put([distances[e.vertex], e.vertex])
	if distances[N - 1] == float('inf'):
		return -1
	return distances[N - 1]
(N, M) = map(int, input().split())
g = Graph(N)
for i in range(M):
	(x, y) = map(int, input().split())
	g.add_edge(x - 1, y - 1, 0)
print(dijkstra(g, 0, N - 1))


import heapq
(n, m) = [int(x) for x in input().split()]
a = [[] for i in range(n)]
for i in range(m):
	(p, q) = [int(x) for x in input().split()]
	if p == q:
		continue
	a[p - 1].append((0, q - 1))
	a[q - 1].append((1, p - 1))
d = [-1] * n
d[0] = 0
q = a[0]
heapq.heapify(q)
while q:
	p = heapq.heappop(q)
	for x in a[p[1]]:
		if d[x[1]] == -1 or d[x[1]] > p[0] + x[0]:
			d[x[1]] = p[0] + x[0]
			heapq.heappush(q, (d[x[1]], x[1]))
print(d[n - 1])


from collections import defaultdict, deque

def main():
	(n, m) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		if u == v:
			continue
		graph[u].append((v, 0))
		graph[v].append((u, 1))
	dist = [float('inf') for i in range(n + 1)]
	queue = deque()
	queue.append(1)
	dist[1] = 0
	while len(queue):
		node = queue.popleft()
		for (neighbour, weight) in graph[node]:
			if dist[node] + weight < dist[neighbour]:
				dist[neighbour] = dist[node] + weight
				if weight == 1:
					queue.append(neighbour)
				else:
					queue.appendleft(neighbour)
	if dist[n] == float('inf'):
		print(-1)
	else:
		print(dist[n])
main()


(n, m) = list(map(int, input().split()))
graph = {i: [] for i in range(1, n + 1)}
for i in range(m):
	(x, y) = list(map(int, input().split()))
	graph[x].append([y, 0])
	graph[y].append([x, 1])
from collections import deque
queue = deque()
dist = [float('inf') for i in range(n + 1)]
queue.append(1)
dist[1] = 0
while queue:
	u = queue.popleft()
	if u == n:
		break
	for (nei, wt) in graph[u]:
		if dist[u] + wt < dist[nei]:
			dist[nei] = dist[u] + wt
			if wt == 1:
				queue.append(nei)
			else:
				queue.appendleft(nei)
if dist[n] != float('inf'):
	print(dist[n])
else:
	print(-1)


from collections import defaultdict
from heapq import heappush, heappop, heapify

def main():
	(n, m) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		if u == v:
			continue
		graph[u].append((v, 0))
		graph[v].append((u, 1))
	dist = [float('inf') for i in range(n + 1)]
	queue = []
	queue.append((0, 1))
	heapify(queue)
	dist[1] = 0
	while len(queue):
		(dis, node) = heappop(queue)
		for (neighbour, weight) in graph[node]:
			if dist[node] != float('inf'):
				if dis + weight < dist[neighbour]:
					dist[neighbour] = dis + weight
					heappush(queue, (dist[neighbour], neighbour))
	if dist[n] == float('inf'):
		print(-1)
	else:
		print(dist[n])
main()


from collections import defaultdict, deque
import math
(n, m) = map(int, input().split())
g = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	if u != v:
		g[u].append([v, 0])
for i in range(1, n + 1):
	for k in g[i]:
		if k[1] == 0:
			g[k[0]].append([i, 1])
q = deque([(1, 0)])
dist = [math.inf] * (n + 1)
dist[1] = 0
visited = set()
while q:
	(a, w) = q.popleft()
	if a not in visited:
		visited.add(a)
		for i in g[a]:
			dist[i[0]] = min(dist[i[0]], dist[a] + i[1])
			if i[1] == 1:
				q.append(i)
			else:
				q.appendleft(i)
if n in visited:
	print(dist[n])
else:
	print(-1)


from collections import *
INF = float('inf')
(n, m) = map(int, input().split())
susjedi = {i: [] for i in range(1, n + 1)}
udaljenost = [INF for i in range(n + 1)]
udaljenost[1] = 0
for i in range(m):
	(x, y) = map(int, input().split())
	susjedi[x].append([y, 0])
	susjedi[y].append([x, 1])
q = deque()
q.append([1, 0])
while q:
	(x, y) = q.popleft()
	for i in susjedi[x]:
		(a, b) = i
		if y + b < udaljenost[a]:
			if b == 0:
				q.appendleft([a, y])
				udaljenost[a] = y
			else:
				q.append([a, y + 1])
				udaljenost[a] = y + 1
if udaljenost[n] != INF:
	print(udaljenost[n])
else:
	print(-1)


(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(v, u) = map(int, input().split())
	v -= 1
	u -= 1
	g[v].append((0, u))
	g[u].append((1, v))
for i in range(n):
	g[i].sort()
used = set()
d = [0] * n
(l, r) = (n, n)
q = [0] * 2 * (n + 1)
used.add(0)
while l <= r:
	v = q[l]
	l += 1
	for (cost, u) in g[v]:
		if cost:
			if u not in used:
				r += 1
				q[r] = u
				d[u] = d[v] + 1
		elif u not in used or d[u] > d[v]:
			l -= 1
			q[l] = u
			d[u] = d[v]
		used.add(u)
print(d[n - 1] if n - 1 in used else -1)


from collections import defaultdict as dd, deque
read = lambda : list(map(int, input().split()))
(m, n) = read()
adj = dd(set)
for _ in range(n):
	(a, b) = read()
	if a == b:
		continue
	adj[a].add((b, 0))
	adj[b].add((a, 1))
q = deque()
q.append(1)
dis = [float('inf')] * (m + 1)
dis[1] = 0
while q:
	u = q.popleft()
	for (v, w) in adj[u]:
		if dis[v] > dis[u] + w:
			dis[v] = dis[u] + w
			if w == 1:
				q.append(v)
			else:
				q.appendleft(v)
if dis[m] == float('inf'):
	print(-1)
else:
	print(dis[m])