def adjecency_matrix(filename, is_oriented=False):
    with open(filename, 'r') as file:
        n, m = file.readline().split()
        n = int(n)
        m = int(m)
        graph = [[0] * (n + 1) for _ in range(n + 1)]
        print(graph)

        for i in range(m):
            x, y = file.readline().split()
            x = int(x)
            y = int(y)

            if x != y:
                graph[x][y] = 1
                if is_oriented == False:
                    graph[y][x] = 1
        return graph


def adjecency_list(filename, is_oriented=False):
    with open(filename, 'r') as file:
        n, m, s = file.readline().split()
        n = int(n)
        m = int(m)
        graph = {i: [] for i in range(n + 1)}

        for i in range(m):
            x, y = file.readline().split()
            x = int(x)
            y = int(y)
            graph[x].append(y)
            if is_oriented == False:
                graph[y].append(x)

        return graph, s


def print_matrix(matrix):
    for row in matrix:
        print(row)


from collections import deque


def bfs(graph, start):
    res = [-1] * (len(graph) - 1)
    vis = set()
    q = deque()
    q.append((start, 0))
    vis.add(start)
    while q:
        node, level = q.popleft()
        res[node - 1] = level
        for child in graph[node]:
            print(child)
            if child not in vis:
                vis.add(child)
                q.append((child, level + 1))

    return res

graph, s = adjecency_list('bfs.in', is_oriented=True)

print(graph)

with open('bfs.out', 'w') as file:
    for i in bfs(graph, int(s)):
        file.write(str(i) + ' ')
        print(i, end=' ')
    print()