#include <bits/stdc++.h>

using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
int n, m, s;
queue <int> k;
int vizi[1000005] ;
int d[1000005];
int *A[1000005];
void BFS(int x)
{
    k.push(x);
    vizi[x]=1;
    d[x]=0;
    while(k.size())
    {for(int i=1;i<=A[k.front()][0];i++)
    {
        if(!vizi[A[k.front()][i]])
        {
            vizi[A[k.front()][i]]=1;
            k.push(A[k.front()][i]);
            d[A[k.front()][i]]=d[k.front()]+1;
        }
    }
    k.pop();
    }
}

int main()
{
    in>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        A[i]= (int *)realloc(A[i], sizeof(int));
        A[i][0]=0;
    }
    for(int i=1;i<=m;i++)
    {
        d[i]=-1;
        int a, b;
        in>>a>>b;
        A[a][0]++;

        A[a]=(int *)realloc(A[a], (A[a][0]+1)*sizeof(int));
        A[a][A[a][0]]=b;

    }
    /*for(int i=1;i<=n;i++)
    {
        cout<<"COAIE"<<i<<":  ";
        for(int j=1;j<=A[i][0];j++)
        {
        cout<<A[i][j]<<" ";
        }
        cout<<endl;
    }*/
    BFS(s);
    for(int i=1;i<=n;i++)
    {
        out<<d[i]<<" ";
    }
    return 0;
}