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

from collections import defaultdict, deque


def bfs(graph, start, end):
    queue = deque([(start, 0)])
    visited = {start: 0}

    while queue:
        node, dist = queue.popleft()
        if node == end:
            return dist

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = dist + 1
                queue.append((neighbor, dist + 1))

    return -1  # 如果找不到终点，返回-1


def build_graph(n, m):
    graph = defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)  # 无向图，双向添加边
    return graph


# 输入数据
n, m = map(int, input().split())
graph = build_graph(n, m)

shortest_distance = bfs(graph, 1, n)
print(shortest_distance)