import math
import queue
from collections import defaultdict


def parse(str, i):
    while i < len(str) and (str[i] < '0' or str[i] > '9'):
        i = i + 1
    num = 0
    str2 = ""
    while i < len(str) and (str[i] >= '0' and str[i] <= '9'):
        str2 += str[i]
        i = i + 1
    num = int(str2)
    return (i, num)


class BFS:
    def __init__(self):
        self.AdjList = defaultdict(list)

    def add_edge(self, x, y):
        self.AdjList[x].append(y)

    def bfs(self, startNode, n):
        distance = [math.inf] * (n + 1)
        q = queue.Queue()
        q.put((startNode, 0))
        distance[startNode] = 0
        while not q.empty():
            top = q.get()
            for child in self.AdjList[top[0]]:
                if distance[child] == math.inf:
                    distance[child] = top[1] + 1
                    q.put((child, distance[child]))
        return distance


def read(grap):
    f = open("bfs.in", "r")
    str = f.read()
    i = 0
    (i, n) = parse(str, i)
    (i, m) = parse(str, i)
    (i, s) = parse(str, i)
    for _ in range(m):
        (i, x) = parse(str, i)
        (i, y) = parse(str, i)
        grap.add_edge(x, y)
    return (s, n)


grap = BFS()
(start_node, n) = read(grap)
distances = grap.bfs(start_node, n)
g = open("bfs.out", "w")
for i in range(len(distances) - 1):
    if (distances[i + 1] != math.inf):
        g.write(str(distances[i + 1]) + " ")
    else:
        g.write(str(-1) + " ")