#include<vector>
#include<fstream>
#include<queue>
#define fin "bfs.in"
#define fout "bfs.out"
using namespace std;

ifstream f(fin);
ofstream p(fout);

#define MAXN 100004

queue<int> Q;
vector<int> T[MAXN];
int c[MAXN];

int n, m, s, nr;


int cit() {
    f >> n;
    f >> m;
    f >> s;

    int x, y;

    for ( int i = 1; i <= m; i++) {
        f >> x;
        f >> y;
        T[x].push_back(y);
    }
    return 0;
}
int bfs (int nod) {
    Q.push(nod);
    c[nod] = 0;

    while ( !Q.empty() ) {
        for ( int i = 0, lung = T[Q.front()].size(); i < lung; i++) {
            if ( c[ T [Q.front()][i] ] == -1 && c[ T[Q.front()][i] ] != 0 ) {
                Q.push( T [Q.front()][i]);
                c [ T[Q.front()][i] ] = c [Q.front()] + 1;
            }
        }
        Q.pop();
    }
    return  0;
}
int write() {
     for (int i = 1; i <= n; i++) {
        p << c[i] << "";
     }
     return 0;
}
int main()
{
    cit();

    for ( int i = 1; i <= n; i++) {
        c[i] = -1;
    }
    bfs(s);
    write();

    return 0;
}