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

using namespace std;

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

void BFS(int nr_noduri, int nr_muchii, int start, vector <pair<int,int>> lista_muchii) {

        queue <int> bfs_tree;
        vector <int> viz;
        for (int i = 0; i <= nr_noduri; i++)
            viz.push_back(-1);

        bfs_tree.push(start);
        viz[start] = 0;

        while (!bfs_tree.empty()) {
            int nod_curent = bfs_tree.front();
            bfs_tree.pop();

            for (int i = 0; i < nr_muchii; i++)
                if (lista_muchii[i].first == nod_curent && viz[lista_muchii[i].second] == -1) {
                    viz[lista_muchii[i].second] = viz[nod_curent] + 1;
                    bfs_tree.push(lista_muchii[i].second);
                }
        }

        for (int i = 1; i <= nr_noduri; i++)
            out << viz[i] << " ";
}

int main()
{
    int n,m,s;
    vector <pair<int,int>> v;

    in >> n >> m >> s;
    for(int i=0; i<m; i++)
    {
        int x,y;
        in >> x >> y;
        v.push_back(make_pair(x,y));
    }

    BFS(n,m,s,v);

    in.close();
    out.close();
    return 0;
}