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

using namespace std;

// Matrice adiacatenta
// Complexitate O(n+m)
// Se dau in ordine numarul n varfuri, numarul m muchii, si m muchii

int n, m, nodstart;
vector<int> tata;
vector<int> dist;
vector<bool> viz;
vector < vector<int>> listaAdiacenta;
ifstream fin("bfs.in");
ofstream fout("bfs.out");


//citire Lista Adiacenta
void citire()
{
    fin >> n >> m>>nodstart;
    int x, y;
    listaAdiacenta = vector<vector<int>>(n+1, vector<int>());
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y;
        listaAdiacenta[x].push_back(y);
        //listaAdiacenta[y].push_back(x);
    }
}

void BFS(int nodStart)
{
    queue<int> coada;
    coada.push(nodStart);
    dist[nodStart] = 0;
    tata[nodStart] = -1;
    viz[nodStart] = true;
    while (!coada.empty())
    {
        int nodCurent = coada.front();
        coada.pop();
        for (auto elem : listaAdiacenta[nodCurent])
        {
            if (viz[elem] == false)
            {
                viz[elem] = true;
                coada.push(elem);
                dist[elem] = dist[nodCurent] + 1;
                tata[elem] = nodCurent;
            }
        }
    }
}

void initializariBfs()
{
    tata = vector<int>(n + 1, -2);
    dist = vector<int>(n + 1, 1e9);
    viz = vector<bool>(n + 1, false);
    BFS(nodstart);
}

void afisareDistante()
{
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] != 1e9)
            fout << dist[i] << " ";
        else
            fout << -1 << " ";
    }
}

// Afisare drum de la start la un nod
void afiseazaDrum(int nod)
{
    if (tata[nod] == -1 || tata[nod]==-2)
    {
        cout << nod;
        return;
    }
    afiseazaDrum(tata[nod]);
    cout << nod;
}

int main()
{
    citire();
    initializariBfs();
    afisareDistante();
}