#include <iostream>
#include <fstream>
#include <list>

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

class Graf{
    int n;
    std::list <int> * ad;
public:
    Graf (int n) : n(n){
        ad = new std::list<int> [n +1];
    }
    void addEdge(int i, int j){
        ad[i].push_back(j);
    }
    void BFS(int i);
};

void Graf::BFS(int i){

    int coada[n+1];
    bool ver[n + 1];
    int pas[n+1];

    for (int j = 1; j <= n ; j ++){
        ver[j] = false;
        pas[j] = -1;
    }

    coada[0] = i;
    ver[i] = true;
    pas[i] = 0;

    int s = 0;
    int d = 1;

    while (s < d){
        int a = coada[s];
        std::list <int> :: iterator f;
        for (f = ad[a].begin(); f != ad[a].end(); f ++){
            if (! ver[*f]){
                coada[d] = *f;
                ver[*f] = true;
                pas[*f] = 1+ pas[a];
                d ++;
            }
        }
        s ++;
    }
    for (int i = 1; i <= n; i ++)
        out << pas[i] << " ";

}

int main()
{

    int n,m, start;
    in >> n >> m >> start;

    Graf graf(n);

    while (m){

        int i, j;
        in >> i >> j;
        graf.addEdge(i,j);

        m --;
    }

    graf.BFS(start);

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