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

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

        queue = []
        cost = [0 for _ in range(max(self.graph) + 1)]

        queue.append(s)
        visited[s] = True

        while queue:
            s = queue.pop(0)

            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    cost[i] = cost[s] + 1
                    visited[i] = True
        for node in self.graph.keys():
            if not visited[node]:
                cost[node] = -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.bfs1(S)[1:]

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