//
//  bfs.cpp
//  Parcurgerea BFS
//
//  Created by Andrei Constantinescu on 2/26/13.
//  Copyright (c) 2013 Andrei Constantinescu. All rights reserved.
//
#define dim 100001

#include <fstream>
#include <vector>
using namespace std;

vector <int> a[dim];
int G[dim],n,m,cost[dim];

int main() {
    int i,k,pr,ul,c[dim],s,x,y;
    
    ifstream f ("bfs.in", ios::in);
    ofstream g ("bfs.out", ios::out);
    
    f>>n>>m>>s;
    
    for(i=1;i<=m;i++) {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
    }
    
    for(i=1;i<=n;i++) {
        G[i] = a[i].size();
        cost[i]=-1;
    }
    
    c[1]=s;
    pr=ul=1;
    cost[s]=0;
    while(pr<=ul) {
        k=c[pr++];
        for(i=0;i<G[k];i++)
            if  (cost[a[k][i]]==-1) {
                c[++ul]=a[k][i];
                cost[a[k][i]]=cost[k]+1;
            }
    }
    
    for(i=1;i<=n;i++)
        g<<cost[i];
    
    return 0;
}