#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

vector<vector<int> > mat(100000);

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

int N,M,nod;
void bfs(int dim)
{
        queue<int> coada;
        coada.push(nod);
        int var,vec[dim];
        for(int i = 1; i <= dim; i++)
                vec[i] = -1;
        vec[nod] = 0;
        while(!coada.empty())
        {
                var = coada.front();
                coada.pop();
                for(auto elem : mat[var])
                {
                        if(vec[elem] == -1)
                        {
                                vec[elem] = vec[var] + 1;
                                coada.push(elem);
                        }
                }
        }
        for(int i = 1; i <= dim; i++)
                out << vec[i] << ' ';
}
int main()
{
        in >> N >> M >> nod;
        int x, y;
        for(int i = 0; i < M; i++)
        {
                in >> x >> y;
                mat[x].push_back(y);
        }
        bfs(N);
        return 0;
}