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

using namespace std;

#define NMAX 100002

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

int N, M, S;
vector <int> G[NMAX];
int shortest_path[NMAX];

void read()
{
    int x, y;
    fin >> N >> M >> S;
    for (int i = 0; i < M; i++)
    {
        fin >> x >> y;
        G[x].push_back(y);
    }
}

void bfs()
{
    memset(shortest_path, -1, sizeof(int) * (N + 1) );
    shortest_path[S] = 0;
    queue <int> path;
    path.push(S);
    int node;
    while (!path.empty())
    {
        node = path.front();
        path.pop();
        for (unsigned int i = 0; i < G[node].size(); i++)
        {
            int curr_node = G[node].at(i);
            if (shortest_path[curr_node] == -1)
            {
                shortest_path[curr_node] = shortest_path[node] + 1;
                path.push(curr_node);
            }
        }
    }
}

void print()
{
    for (int i = 1; i <= N; i++)
    {
        fout << shortest_path[i] << ' ';
    }
}

int main()
{
    read();
    bfs();
    print();
}