from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(5001)]
for i in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
    g[v].append(u)
# print(g)
if len(g[1])==0:
    print(-1)
else:
    a=deque()
    b=-1
    c=[1]
    for i in g[1]:
        a.append([i,1])
    g[1]=[]
    while a and b==-1:
        # print(a)
        x,ans=a.popleft()
        if x not in c:
            c.append(x)
            for i in g[x]:
                if i==n:
                    b=ans+1
                    break
                else:
                    # if [i,ans+1] not in a:
                        a.append([i,ans+1])
    print(b)

我真服了概率提交成功