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

n, m = map(int, input().split())
c = [[] for _ in range(5000)]
d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append((a,b))
    a, b = a-1, b-1
    c[a].append(b)
    c[b].append(a)
#print(c)
def count(n):
    d = [0]
    e = []
    f = {0}
    j = 0
    while len(d) != 0:
        j += 1
        for x in d:
            for y in c[x]:
                if y == n-1:
                    return j
                elif y not in f:
                    f.add(y)
                    e.append(y)
        d = e
        e = []
    return -1
print(count(n))