from queue import Queue

f = open("bfs.in", "r")
g = open("bfs.out", "w+")


def bfs(start, q, lista_adiacenta, vizitat, distanta):
    q.put(start)

    while q.empty() == 0:
        arc = q.get()
        for vecin in lista_adiacenta[arc]:
            if vizitat[int(vecin)] == 0:
                distanta[int(vecin)] = distanta[int(arc)] + 1
                vizitat[int(vecin)] = 1
                # g.write(vecin + " ")
                q.put(vecin)


def main():
    lista = [x for x in f.readline().split()]
    # print(lista)
    nr_varfuri = int(lista[0])
    nr_arce = int(lista[1])
    nod_sursa = lista[2]
    lista_adiacenta = {}

    for i in range(nr_arce):
        muchie = [f.readline().split()]
        # print(muchie)
        if muchie[0][0] != muchie[0][1]:
            if lista_adiacenta.get(muchie[0][0]) is None:
                lista_adiacenta.update({muchie[0][0]: list(muchie[0][1])})
            else:
                lista_adiacenta[muchie[0][0]].append(muchie[0][1])

    # print(lista_adiacenta)

    q = Queue(maxsize=nr_arce)
    vizitat = [0] * (nr_varfuri + 1)
    vizitat[int(nod_sursa)] = 1
    distanta = [0] * (nr_varfuri + 1)

    bfs(nod_sursa, q, lista_adiacenta, vizitat, distanta)

    for i in range(len(vizitat)):
        if vizitat[i] == 0:
            distanta[i] = -1
    distanta = distanta[1:]
    distanta = " ".join(str(x) for x in distanta)
    # print(distanta)
    g.write(distanta)

    f.close()


if __name__ == "__main__":
    main()