#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int n,m,s,x,y;
vector <int> a[100001];
int q[100001],cost[100001],p,u;
void add_vecini(int el);
bool viz[100001];
int nre[100001];
int main()
{

    f>>n>>m>>s;
    for(int i=1;i<=m;i++){
        f>>x>>y;
        a[x].push_back(y);
        ++nre[x];
    }
    memset(cost,-1,sizeof(cost));
    q[1]=s;
    cost[s]=0;
    viz[s]=1;
    p=u=1;
    while(p<=u){
            add_vecini(q[p]);
            p++;
    }
    for(int i=1;i<=n;i++)
        g<<cost[i]<<' ';
    return 0;
}


void add_vecini(int el){
    for(int i=0;i<nre[el];i++){
        if(viz[a[el][i]]==0){
            viz[a[el][i]]=1;
            q[++u]=a[el][i];
            cost[a[el][i]]=cost[q[p]]+1;
        }
    }
}