#include <stdio.h>
#include <bitset>
#include <deque>

using namespace std;
FILE* f, * g;
int start[1000002], t[3][2000004];
bitset <1000002>viz;
int drum[1000002];
deque <int> q;

int main()
{
    int x, i, j, m, n, o, k = 0, nod, ss, no;
    f = fopen("bfs.in", "r");
    g = fopen("bfs.out", "w");
    fscanf(f, "%d %d %d", &n, &m, &x);
    for (o = 1;o <= m;++o)
    {
        fscanf(f, "%d %d", &i, &j);
        ++k;
        t[0][k] = j;
        t[1][k] = start[i];
        start[i] = k;
    }
    for (i = 1;i <= n;++i)
        drum[i] = 2000000000;
    q.push_back(x);///introduc nodul de la care pornesc in coada
    viz[x] = 1;///am vizitat acel nod
    drum[x] = 0;///distanta pana acum e 0
    while (!q.empty())
    {
        nod = q.front();///noul nod din coada
        q.pop_front();///eliminam nodul
        no = start[nod];
        ss = drum[nod];///distanta pana la nodul nod
        while (no)///parcurg toti vecinii nodului nod
        {
            if (viz[t[0][no]] == 0 && ss + 1 < drum[t[0][no]])///daca nu am mai trecut prin acel nod vecin sau daca am gasit o distanta mai mica pana la acela
            {
                q.push_back(t[0][no]);///introduc noul nod in coada
                drum[t[0][no]] = ss + 1;///noua distanta
                viz[t[0][no]] = 1;///marchez acel vecin ca vizitat
            }
            no = t[1][no];
        }
    }
    for (i = 1;i <= n;++i)
    {
        if (drum[i] != 2000000000)
            fprintf(g, "%d ", drum[i]);
        else
            fprintf(g, "-1 ");
    }


    fclose(f);
    fclose(g);
    return 0;
}