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

using namespace std;

const int NMAX = 1e6;
vector <int> G[NMAX+1];
queue <int> coada;
int C[NMAX+1];

void BFS(int s){
    coada.push(s);
    while(!coada.empty()){
        for(auto x:G[s])
        {
            if(C[x]< 0){
                coada.push(x);
                C[x] = C[s]+1;
            }
        }
        coada.pop();
        s = coada.front();
    }
}

int main(){
    ifstream f("bfs.in");
    int n, m, s;
    f>>n>>m>>s;
    for(int i=1; i<=m; i++){
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
    }
    f.close();
    for(int i=1; i<=n; i++){
        C[i] = -1;
    }
    C[s] = 0;
    BFS(s);
    ofstream g("bfs.out");
    for(int i=1; i<=n; i++){
        g<<C[i];
    }
    g.close();
}