from collections import defaultdict


class Graph:

    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def bfs(self, s):
        visited = [False] * (max(self.graph) + 1)

        queue = []
        road = set()
        cost = [0 for x in range(max(self.graph))]

        queue.append(s)

        visited[s] = True

        while queue:
            s = queue.pop(0)
            road.add(s)
            # print(s, end=" ")

            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    cost[i - 1] = cost[s - 1] + 1
                    visited[i] = True
        for node in set(self.graph.keys()).difference(road):
            cost[node-1] = -1

        return cost

file = 'bfs.in'

with open(file, 'rt') as f:
    content = f.readlines()
    content = [line.strip().split() for line in content]
    content = [[int(x) for x in line] for line in content]
    N, M, S = content[0][0], content[0][1], content[0][2]

g = Graph()
for edges in content[1:]:
    g.addEdge(edges[0], edges[1])

result = g.bfs(S)

with open('bfs.out', 'wt') as f:
    for c in result[0:-1]:
        f.write(str(c))
        f.write(' ')
    f.write(str(result[-1]))