//Infoarena. Arhiva Educationala. Parcurgerea in Latime.
#include<iostream>
#include<fstream>
using namespace std;

int G[10005][10005];
bool visited[100005];
void roy_floyd(int[][10005],int);

int main(){
    freopen("bsf.in","r",stdin);
    freopen("bsf.out","w",stdout);
    int N,M,S;
    cin>>N>>M>>S;

    int x,y;
    for(int i=1;i<=M;i++){
        cin>>x>>y;
        G[x][y]=1;
    }

    roy_floyd(G,N);
    for(int i=1;i<=N;i++){
        if(i==S) cout<<"0 ";
        else if(G[S][i]==0) cout<<"-1 ";
              else cout<<G[S][i]<<" ";
    }

}

void roy_floyd(int G[10005][10005],int N){
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++){
                if(i!=j && G[i][k] && G[k][j] &&
                   (!G[i][j] || G[i][j]>G[i][k]+G[k][j]) )
                   G[i][j]=G[i][k]+G[k][j];
            }
}