#include <cstdlib>
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>

using namespace std;


void bfs(int S, const vector< list<int> > &neighbors, vector<int> &visited, vector<int> &d)
{
    queue<int> Q;

    d[S]        = 0;
    visited[S]  = 1;
    Q.push(S);

    while (!Q.empty())
    {
        int node = Q.front();
        Q.pop();

        for (list<int>::const_iterator it = neighbors[node].begin(); it != neighbors[node].end(); ++it)
        {
            if (!visited[*it])
            {
                visited[*it] = 1;
                d[*it]       = 1 + d[node];
                Q.push(*it);
            }
        }
    }
}


int main()
{
    vector< list<int> >   neighbors;
    vector<int>             d, visited;
    int                     M, N, S;
    int                     a, b;
    fstream                 f, g;

    f.open("bfs.in", ios::in);
    g.open("bfs.out", ios::out);

    f >> N >> M >> S;
    S--;
    neighbors.resize(N, list<int>());
    visited.resize(N, 0);
    d.resize(N, -1);
    for (int i = 0; i < M; i++)
    {
        f >> a >> b;
        if (a != b) neighbors[a-1].push_back(b-1);
    }

    bfs(S, neighbors, visited, d);

    for (vector<int>::iterator it = d.begin(); it != d.end(); ++it)
    {
        g << *it << " ";
    }

    f.close();
    g.close();

    return 0;
}