#include <fstream>
#include <cstring>
#include <vector>
#include <deque>

#define MAX 100001

using namespace std;

vector <int> v[MAX];
deque <int> q;
int use[MAX],D[MAX];
int N,S;

inline void Read()
{
    int M,x,y;
    ifstream in;

    in.open("bfs.in");

    in>>N>>M>>S;
    for(;M;--M)
    {
        in>>x>>y;
        v[x].push_back(y);
    }

    in.close();
}

inline void bf(int nod)
{
    vector <int>::iterator it;

    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(!use[*it])
        {
            D[*it]=D[nod]+1;
            use[*it]=1;
            q.push_back(*it);
        }

    if(q.size())
    {
        nod=q.front();
        q.pop_front();
        bf(nod);
    }
}

inline void BFS()
{
    memset(use,0,sizeof(use));
    memset(D,-1,sizeof(D));

    D[S]=0;
    use[S]=1;
    bf(S);
}

inline void Write()
{
    ofstream out;

    out.open("bfs.out");

    for(int i=1;i<N;i++)
        out<<D[i]<<' ';
    out<<D[N]<<'\n';

    out.close();
}

int main()
{
    Read();
    BFS();
    Write();

    return 0;
}