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

using namespace std;
FILE* f, * g;
int start[1000002], t[3][2000004];
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);
    drum[x] = 0;
    while (!q.empty())
    {
        nod = q.front();
        q.pop_front();
        no = start[nod];
        ss = drum[nod];
        while (no)
        {
            if (ss + 1 < drum[t[0][no]])
            {
                q.push_back(t[0][no]);
                drum[t[0][no]] = ss + 1;
            }
            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;
}