#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    int  N, S, a, b;
    long int M;
    f >> N >> M >> S;
    vector<vector<int> > v(N+1);
    for (int i = 0; i < M; i++){
        f >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1; i < N; i++){
        printf("%d: ",i);
        for (int j = 0; j < v[i].size(); j++)
            printf("%d ", v[i][j]);
        printf("\n");
    }
    vector<int> costuri(N+1,-1); 
    vector<int> viz(N+1, 0);
    queue<pair<int, int> > q;
    pair<int, int> current;
    int cost = 0;
    cost++;
    viz[S] = 1;
    costuri[S] = 0;
    for (int j = 0; j < v[S].size(); j++){
        if (v[S][j] == S){
            costuri[S] = 0;
            continue;
        }
        q.push(make_pair(v[S][j], cost));
        viz[v[S][j]] = 1;
    }

    while (!q.empty()){
        current = q.front();
        viz[current.first] = 1;
        costuri[current.first] = current.second;
        q.pop();
        for (int j = 0; j < v[current.first].size(); j++)
            if (viz[v[current.first][j]] == 0){
                q.push(make_pair(v[current.first][j],current.second+1));
                viz[v[current.first][j]] = 1;
            }
    }

    for (int i = 1; i < N; i++)
        g << costuri[i] << " ";
    g << costuri[N];
    return 0;
}