#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>

using namespace std;

struct elem
{
    int nod;
    int rang;
    elem(int x = 0, int y = 0)
    {
        nod = x;
        rang = y;
    }
};

deque <elem> coada;
vector <int> a[100009];
int v[100009];
int n, m, s;

void citire()
{
    int i, x, y;
    scanf("%d%d%d", &n, &m , &s);
    s--;
    for(i = 0; i < n; i++)
        v[i] = -1;
    for(i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        a[x-1].push_back(y-1);
    }
}

void solve()
{
    coada.push_back(elem(s, 0));
    v[s] = 0;
    int crt, rang, i, aux;
    while(!coada.empty())
    {
        crt = coada.front().nod;
        rang = coada.front().rang;
        for(i = 0; i < a[crt].size(); i++)
        {
            aux = a[crt][i];
            if(v[aux] < 0)
            {
                v[aux] = rang + 1;
                coada.push_back(elem(aux, rang+1));
            }
        }

        coada.pop_front();
    }
}

int main()
{
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    citire();
    solve();
    for(int i = 0; i < n; i++)
        printf("%d ", v[i]);
    return 0;
}