#include <bits/stdc++.h>

using namespace std;

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

vector < vector <int> > g;

vector <int> dist;

vector <bool> v;

int main()
{
    int n, m, s, x, y;

    fin >> n >> m >> s;

    g.resize(n + 1), dist.resize(n + 1, -1), v.resize(n + 1);

    while(fin >> x >> y) {
        g[x].push_back(y);
    }

    fin.close();

    queue <int> q;

    q.push(s);
    v[s] = true, dist[s] = 0;

    while(!q.empty()) {
        for(int nod : g[q.front()]) {
            if(!v[nod]) {
                dist[nod] = dist[q.front()] + 1;
                v[nod] = true;
                q.push(nod);
            }
        }

        q.pop();
    }

    for(vector<int> :: iterator it = dist.begin() + 1; it < dist.end(); it++)
        fout << *it << " ";

    fout.close();

    return 0;
}