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

import sys
from collections import deque  #双端队列

n, m = map(int, input().split())  # 获得数据的m和n
map_grid = [[] for _ in range(5000)]  #建立一个顶点表（记录各个顶点信息）
for i in range(m):     # 开始往顶点表里面填充
    u, v = map(int, input().split())
    u, v = u-1, v-1
    map_grid[u].append(v)   #意思就是，有0~4999的顶点，然后，将能够与这些点相连的点放进对应的数组里面
    map_grid[v].append(u)

root1 = [i for i in range(5000)]   # 我发现只有这样才能快，root1代表是没有遍历过的点


def routine(n, root1, map_grid):
    flag = 0
    root2 = deque([0])  #构建一个双端队列，root2是代表即将遍历的点，因为从点1开始遍历，对应到顶点表，就是第0个点。
    visited = {}   #字典，用来判断点有没有被遍历过
    while root2:  # 待遍历的队列里面还有值，就进入循环，没有值就退出
        for _ in range(len(root2)): # 开始遍历root2里面的所有点，一开始就是从0开始
            i = root2.popleft()  #将root2中最前面的点从待遍历队列里面弹出来
            visited[i] = True  #并设置这个点的状态是已经遍历过了
            if i == n - 1:  # 如果遍历的这个点就是终点，那就可以结束循环了。直接输出路径
                return flag
            
            for j in root1:   # 接着就是以i点为顶点，开始在还没有遍历过的点里面找跟它有路的点
                if j in map_grid[i] and not visited.get(j):#这里的判断就是：j点如果在以i点为顶点的定点表里面，并且它没有被遍历过，那就把j放进待遍历的表里面，等待搜索
                    root2.append(j)  # 这里就是把j点放进待遍历的列表里面
                    visited[j] = True  # 将这个点的状态标记未已经遍历过了
                    root1.remove(j)  #节约时间，如果这个点进入了待遍历列表里面，就从未遍历的列表里面删除
            
        flag += 1 #从i点能够找到下线，就完成了一层的遍历，路径+1
    return -1  #如果root2里面都没有值了，没有输出，那就输出-1


print(routine(n, root1, map_grid))