#include <bits/stdc++.h>
using namespace std;
ifstream fcin("bfs.in");
ofstream fcout("bfs.out");

vector<int>nod[100003];
queue<int>coada;
int n,m,x,y,s;
int dist[100003]; //de ce nu merge int dist[100003]={-1}; ?
bool ap[100003];

void init()
{
    for(int i=1;i<=n;i++)
        dist[i]=-1;
}

void BFS(int a, int d)
{
    if(a==0)
        return;
    int b=0,c;
    //cout<<endl<<"nrel-"<<a<<endl;
    for(int i=1;i<=a;i++){
        c=coada.front();
        if(!ap[c]){
            ap[c]=1;
            dist[c]=d;
//            cout<<c<<' ';
            for(int j=0;j<nod[c].size();j++){
                if(!ap[nod[c][j]]){
                    coada.push(nod[c][j]);
                    b++;
                }
            }
        }
        coada.pop();
    }
    BFS(b,++d);
}

int main()
{
    fcin>>n>>m>>s;
    init();
    for(int i=1;i<=m;i++){
        fcin>>x>>y;
        nod[x].push_back(y);
//        nod[y].push_back(x);
    }

    coada.push(s);
    BFS(1,0);

//    cout<<endl<<endl<<endl;
    for(int i=1;i<=n;i++)
        fcout<<dist[i]<<' ';
    return 0;
}