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

using namespace std;

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

const int NMAX = 100005;
const int INF = -1;

vector<int> G[NMAX];
int dist[NMAX];

int main()
{
    int V, E, Start;
    fin >> V >> E >> Start;

    for(int i = 0 ; i < E; i++)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }
    for(int i = 1; i <= V; i++)
    {
        dist[i] = INF;
    }

    queue<int> coada;
    coada.push(Start);
    dist[Start] = 0;
    while(!coada.empty())
    {
        int curr = coada.front();
        coada.pop();
        for(int vecin : G[curr])
        {
            if(dist[vecin] == INF)
            {
                dist[vecin] = dist[curr] + 1;
                coada.push(vecin);
            }            
        }
    }
    for(int i = 1; i <= V; i++)
    {
        fout << dist[i] << " ";
    }
    fout << endl;
    fin.close();
    fout.close();
    return 0;
}



// BFS classic
// void adaugaMuchie(vector<int> listaAdiacenta[], int u, int v)
// {
//     listaAdiacenta[u].push_back(v);
//     listaAdiacenta[v].push_back(u);
// }
// vector<int> BFS(vector<int> listaAdiacenta[], int nrNoduri, int start)
// {
//     queue<int> coada;
//     vector<int> rez;
//     vector<bool> vizitat(nrNoduri, false);
//     vizitat[start] = true;
//     coada.push(start);
//     while(!coada.empty())
//     {
//         int curr = coada.front();
//         coada.pop();
//         rez.push_back(curr);
//         for(int vecin : listaAdiacenta[curr])
//         {
//             if(!vizitat[vecin])
//             {
//                 vizitat[vecin] = true;
//                 coada.push(vecin);
//             }
//         }
//     }
//     return rez;
// }
// int main() {
//     const int nrNoduri = 7;  
//     vector<int> listaAdiacenta[nrNoduri];
//     adaugaMuchie(listaAdiacenta, 0, 1);
//     adaugaMuchie(listaAdiacenta, 0, 2);
//     adaugaMuchie(listaAdiacenta, 1, 3);
//     adaugaMuchie(listaAdiacenta, 1, 4);
//     adaugaMuchie(listaAdiacenta, 2, 5);
//     adaugaMuchie(listaAdiacenta, 4, 5);
//     vector<int> rezultatBFS = BFS(listaAdiacenta, nrNoduri, 0);
//     cout << "\nOrdinea BFS: ";
//     for (int nod : rezultatBFS) {
//         cout << nod << " ";
//     }
//     cout << endl;
//     return 0;
// }

// Conversie lista <-> matrice
// void listeToMatrice(int n, vector<int> adj[MAX], int a[MAX][MAX]) {
//     for (int i = 1; i <= n; i++) {
//         for (int j = 1; j <= n; j++) {
//             a[i][j] = 0;
//         }
//     }
//     for (int i = 1; i <= n; i++) {
//         for (size_t k = 0; k < adj[i].size(); k++) {
//             int v = adj[i][k];
//             a[i][v] = 1;
//         }
//     }
// }
// void matriceToListe(int n, int a[MAX][MAX], vector<int> adj[MAX]) {
//     for (int i = 1; i <= n; i++) {
//         adj[i].clear();
//     }
//     for (int i = 1; i <= n; i++) {
//         for (int j = 1; j <= n; j++) {
//             if (a[i][j] == 1) {
//                 adj[i].push_back(j);
//             }
//         }
//     }
// }

// Lista de adiacenta
// const int MAX = 10001;
// void construiesteListe(const char* numeFisier, vector<int> graf[], int &n, int tip)
// {
//     ifstream fin(numeFisier);
//     int m, x, y;
//     fin >> n >> m;
//     for(int i = 1; i <= n; i++)
//     {
//         graf[i].clear();
//     }
//     for(int i = 0; i < m; i++)
//     {
//         fin >> x >> y;
//         graf[x].push_back(y);
//         if(tip == 0)
//         {
//             graf[y].push_back(x);
//         }
//     }
//     fin.close();
// }
// void afiseazaListe(vector<int> graf[], int &n)
// {
//     for(int i = 1; i <= n; i++)
//     {
//         cout << "Nodul " << i << " are vecinii: ";
//         if(graf[i].size() == 0)
//         {
//             cout << "(niciun vecin)" << endl;
//         }
//         else
//         {
//             for(int j{0}; j < graf[i].size(); j++)
//             {
//                 cout << graf[i][j] << " ";
//             }
//             cout << endl;
//         }
//     }
// }
// int main() {
//     int n;
//     vector<int> adj[MAX];
//     cout << "--- Graf Neorientat ---" << endl;
//     construiesteListe("graf.in", adj, n, 0);
//     afiseazaListe(adj, n);
//     cout << endl;
//     cout << "--- Graf Orientat ---" << endl;
//     construiesteListe("graf.in", adj, n, 1);
//     afiseazaListe(adj, n);
//     return 0;
// }

// Matrice de adiacenta
// const int MAX = 101;
// void construiesteMatr(const char* numeFisier, int a[MAX][MAX], int &n, int tip)
// {
//     ifstream fin(numeFisier);
//     if(!fin)
//     {
//         cout << "Nu s-a putut deschide fisierul";
//         return;
//     }
//     int m;
//     fin >> n >> m;
//     for(int i = 1; i <= n; i++)
//     {
//         for(int j = 1; j <= n; j++)
//         {
//             a[i][j] = 0;
//         }
//     }
//     int x, y;
//     for(int i = 1; i <= m; i++ )
//     {
//         fin >> x >> y;
//         a[x][y] = 1;
//         if(tip == 0)
//         {
//             a[y][x] = 1;
//         }
//     }
//     fin.close();
// }
// void afisareMatr(int a[MAX][MAX], int n)
// {
//     for(int i = 1; i <= n; i++)
//     {
//         for(int j = 1; j <= n; j++)
//         {
//             cout << a[i][j] << " ";
//         }
//         cout << endl;
//     }
// }
// int main()
// {
//     int a[MAX][MAX], n;
//     construiesteMatr("graf.in", a, n, 1);
//     cout << "Matricea adiacenta este: "<< endl;
//     afisareMatr(a, n);
//     return 0;
// }