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

using namespace std;

vector<vector<int>> citireGrafMatrice(string numeFisier, bool orientat, ifstream &in)
{
    int m, n;
    in >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            a[i][j] = 0;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        a[x][y] = 1;
        if (orientat == false)
            a[y][x] = 1;
    }
    return a;
}

vector<vector<int>> citireGrafListe(string numeFisier, bool orientat, ifstream &in)
{
    int m, n;
    in >> n >> m;
    vector<vector<int>> liste(n + 1);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        liste[x].emplace_back(y);
        if (orientat == false)
            liste[y].emplace_back(x);
    }
    return liste;
}

void printMatrice(vector<vector<int>> matrice)
{
    for (int i = 1; i < matrice.size(); i++)
    {
        for (int j = 1; j < matrice[i].size(); j++)
            cout << matrice[i][j] << " ";
        cout << endl;
    }
}

void printListe(vector<vector<int>> liste)
{
    for (int i = 1; i < liste.size(); i++)
    {
        cout << i << " : ";
        for (int j = 0; j < liste[i].size(); j++)
        {
            cout << liste[i][j] << " ";
        }
        cout << endl;
    }
}

vector<vector<int>> listaLaMatrice(vector<vector<int>> liste, bool orientat)
{
    vector<vector<int>> matrice(liste.size(), vector<int>(liste.size(), 0));
    for (int i = 1; i < liste.size(); i++)
    {
        for (int j = 0; j < liste[i].size(); j++)
        {
            matrice[i][liste[i][j]] = 1;
            if (orientat == false)
                matrice[liste[i][j]][i] = 1;
        }
    }
    return matrice;
}

vector<vector<int>> matriceLaLista(vector<vector<int>> matrice, bool orientat)
{
    vector<vector<int>> liste(matrice.size());
    for (int i = 1; i < matrice.size(); i++)
    {
        for (int j = 1; j < matrice.size(); j++)
        {
            if (matrice[i][j] == 1)
                liste[i].emplace_back(j);
        }
    }
    return liste;
}

void bfs(vector<vector<int>> liste, int s, vector<int> &drum, vector<int> &tati)
{
    queue<int> coada;
    vector<bool> vizitat(liste.size(), false);
    for (int i = 0; i < liste.size(); i++)
        drum.emplace_back(-1);
    for (int i = 0; i < liste.size(); i++)
        tati.emplace_back(-1);
    coada.push(s);
    vizitat[s] = true;
    drum[s] = 0;
    tati[s] = 0;

    while (!coada.empty())
    {
        int nod = coada.front();
        // cout << nod << " ";
        coada.pop();
        for (int i = 0; i < liste[nod].size(); i++)
        {
            if (vizitat[liste[nod][i]] == false)
            {
                coada.push(liste[nod][i]);
                vizitat[liste[nod][i]] = true;
                drum[liste[nod][i]] = drum[nod] + 1;
                tati[liste[nod][i]] = nod;
            }
        }
    }
}

void dfs(int x)
{
}

int main()
{
    // bool orientare = true;
    // vector<vector<int>> liste = citireGrafListe("graf.in", orientare);
    // vector<vector<int>> matrice = citireGrafMatrice("graf.in", orientare);
    // printMatrice(matrice);
    // cout << endl;
    // printMatrice(listaLaMatrice(liste, orientare));
    // cout << endl;
    // printListe(liste);
    // cout << endl;
    // printListe(matriceLaLista(matrice, orientare));
    // cout << endl;
    // vector<int> drum;
    // vector<int> tati;
    // bfs(liste, 2, drum, tati);
    // cout << endl;
    // for (int i = 1; i < drum.size(); i++)
    //     cout << tati[i] << " ";
    // cout << endl;
    // for (int i = 1; i < drum.size(); i++)
    //     cout << drum[i] << " ";
    // int s, x;
    // cout << endl;
    // cin >> s >> x;
    // bfs(liste, s, drum, tati);
    // cout << endl;
    // if (tati[x] == -1)
    //     cout << "Nu exista drum.";
    // else
    // {
    //     vector<int> arce;
    //     arce.emplace_back(x);
    //     while (x != s)
    //     {
    //         arce.emplace_back(tati[x]);
    //         x = tati[x];
    //     }
    //     cout << endl;
    //     for (int i = arce.size() - 1; i >= 0; i--)
    //         cout << arce[i] << " ";
    // }

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

    int n, m, s;
    in >> n >> m >> s;

    vector<vector<int>> liste(n + 1);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        liste[x].emplace_back(y);
    }
    vector<int> drum;
    vector<int> tati;
    bfs(liste, s, drum, tati);
    for (int i = 1; i < drum.size(); i++)
        out << drum[i] << " ";
    return 0;
}