#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

queue <int> q;
vector < int > V[1000001];
int C[1000001], Ap[1000001];
int N, M, S;

int main()
{
    int x, y;
    fin>>N>>M>>S;
    for(int i=1; i<=M; i++)
    {
        fin>>x>>y;
        V[x].push_back(y);
    }
    for(int i=1; i<=N; i++)
    {
        Ap[i]=V[i].size();//nr de noduri conectate
    }

    q.push(S);
    C[S]=1;
    while(!q.empty())
    {
        S=q.front();
        //cout<<S<<" ";
        for(int i=0; i<Ap[S]; i++)
        {
            if(C[V[S].operator[](i)]==0)
            {
                C[V[S].operator[](i)]=C[S]+1;
                q.push(V[S].operator[](i));
            }
        }
        q.pop();
    }

    for(int i=1; i<=N; i++)
    {
        fout<<C[i]-1<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}