from collections import defaultdict import heapq ins=[] while True: try: ins.append(list(input().split())) except: break n,m=[int(val) for val in ins[0]] data=ins[1:] def dijkstra(n,m,data): edges=defaultdict(list) for mi in range(m): di=[int(val) for val in data[mi]] edges[di[0]].append((di[1],1)) edges[di[1]].append((di[0],1)) visited=[0]*5001 alls=[(0,1)]#cost,node while alls: cost,node=heapq.heappop(alls) if node==n: return cost visited[node]=1 for nbi,costi in edges[node]: if visited[nbi]==0: heapq.heappush(alls,(cost+costi,nbi)) return -1 if __name__ == '__main__': print (dijkstra(n,m,data))