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

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

const int Nmax = 1e5+7;
int N, M, S, viz[Nmax], d[Nmax];
vector <int> v[Nmax];
queue <int> Q;

void bfs(int node) {
    viz[node] = 1;
    Q.push(node);
    while(!Q.empty()) {
        int n = Q.front();
        Q.pop();
        vector <int> :: iterator it;
        for(it = v[n].begin(); it != v[n].end(); ++it)
            if(!viz[*it]) {
                viz[*it] = 1;
                d[*it] = d[n] + 1;
                Q.push(*it);
            }
    }
}

int main() {
    cout << Nmax;
    fin >> N >> M >> S;
    int x, y;
    while(M--) {
        fin >> x >> y;
        v[x].push_back(y);
    }
    bfs(S);
    for(int i = 1; i <= N; i++)
        (!d[i] && i != S) ? fout << "-1 " : fout << d[i] << " ";
}