题解 | #【模板】单源最短路1#

from collections import *
from math import *
from heapq import *
n,m = map(int,input().split())
g = [deque() for i in range(5001)]
st = [0 for i in range(5001)]
dist = [inf for i in range(5001)]
for i in range(m):
    a,b = map(int,input().split())
    g[a].append((b,1))
    g[b].append((a,1))
def dijkstra():
    dist[1] = 0
    pq = []
    heappush(pq,(0,1))
    while pq:
        distance,ver = heappop(pq)
        if st[ver] == 1:
            continue
        st[ver] = 1
        for t,l in g[ver]:
            if dist[t] > distance + l:
                dist[t] = distance + l
                heappush(pq,(dist[t],t))
    if dist[n] == inf:
        return -1
    return dist[n]    
print(dijkstra())