#include <iostream>
#include <vector>
#include<queue>
#include<fstream>
#define NMAX 100000
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
//vector in care salvez lista de vecini
vector<int>vecini[NMAX];
// cost= vector de "distante"; initial am incercar cu vector<int> cost , dar am avut probleme cu indici
int cost[NMAX];
queue<int>coada;
int n,m,s;
void BFS()
{
    int s1,s2;
    //initializam vectorul de costuri cu -1
    for(int i=1; i<=n; i++)
        cost[i]=-1;
//primul nod de la care plecam va avea mereu costul 0
    cost[s]=0;
    //punem nodul in coada
    coada.push(s);
//daca coada nu este goala
    while(!coada.empty())
    {//extragem primul element din coada(in s2) si il scoatem din coada
        s1=coada.front();
        coada.pop();
        //parcurgem fiecare vecin al nodului curent
        for(int i=0; i< vecini[s1].size(); i++)
        {//s2 ia valoarea vecinului
            s2=vecini[s1][i];
            //daca nu a fost parcurs, il introducem in coada si crestem costul
            if(cost[s2]==-1)
            {
                coada.push(s2);
                cost[s2]=cost[s1]+1;
            }

        }
    }

}

int main()
{
    f>>n>>m>>s;
//citim din fisier in vector
    for(int i=1; i<=m; i++)
    {
        int x,y;
        f>>x>>y;
        //deoarece este graf orientat, punem muchie doar intr-o directie
        vecini[x].push_back(y);



    }
    f.close();


    BFS();
    for(int i=1; i<=n; i++)
        g<<cost[i]<<" ";
    return 0;
}