#include <bits/stdc++.h>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

class Graf
{
private:
    int nrNoduri;
    vector<vector<int>> matrAdiacenta;

public:
    Graf(int N, vector<vector<int>> & matrice);
    void BFS(int nodStart);
    void DFS(int nodStart);
    /*vector<vector <int>> getMatrAdiacenta()
    {
    return matrAdiacenta;
}*/
};

Graf :: Graf(int N, vector<vector<int>> & matrice)
    {
     nrNoduri = N;
     matrAdiacenta = matrice;
    }


void Graf :: BFS(int nodStart)
     {
        queue<int> Q;
        int x, y;
        vector<int> distanta(nrNoduri+1, -1);

        distanta[nodStart] = 0;
        Q.push(nodStart);
        while (!Q.empty())
            {
               x = Q.front();   //eliminam nodul curent din coada
               Q.pop();

               for (int i = 1; i < matrAdiacenta[x].size(); ++i)
                //daca nu au mai fost vizitati si a fost gasit astfel drum mai scurt
                if (distanta[matrAdiacenta[x][i]] == -1)
                {
                   distanta[matrAdiacenta[x][i]] = distanta[x] + 1;
                   Q.push(matrAdiacenta[x][i]);
                }
            }

        for (int i = 1; i <= nrNoduri; ++i)   {
                fout << distanta[i] << " ";
        }
    }

void Graf :: DFS(int x)
{
    vector<bool> vizitat(nrNoduri+1, 0);
    vizitat[x] = 1;
    for(int i = 1; i < matrAdiacenta[x].size(); i++)
        if(vizitat[i] == 0)
            DFS(i);
}


int main()
{   int N, M, S;
    int x, y;
    fin >> N >> M >>S;
    vector<vector<int>> matriceCitita;
    vector<int> aux(1,-1);
    matriceCitita.resize(N+1, aux);
    for (int i = 1; i <= M; ++i){
            fin >> x >> y;
            matriceCitita[x].push_back(y);
        }

    Graf graf(N, matriceCitita);
  /*   for (int i = 1; i < graf.getMatrAdiacenta().size(); ++i){
         for (int j = 1; j < graf.getMatrAdiacenta()[i].size(); ++j){
           fout<< graf.getMatrAdiacenta()[i][j]<<" ";
        }
        fout<<"\n";
  }*/
    graf.DFS(S);
    return 0;
}