#include <fstream>
#include <deque>
#include <vector>
#include <iterator>
#define mn 100006 //max n
using namespace std;

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

vector<int> adiacent[mn];
int Sol[mn], Coada[mn], LG[mn];
int m,n,Start;

void Read()
{int a1,a2;
    f>>n>>m>>Start;
    for(int i=0;i<m;++i)
        {
            f>>a1>>a2;
            adiacent[a1].push_back(a2);
        }

}

void Print()
{
   for(int i=1;i<=n;++i)
        g<<Sol[i]<<' ';
}

void CreateLG()
{
    for(int i=1;i<=n;i++)
        LG[i]=adiacent[i].size();
}

void BFS()
{
    for(int i=1;i<=n;i++)
        Sol[i]=-1;
    Sol[Start]=0;
    Coada[1]=Start;
    int L=1;
    for(int i=1;i<=L;++i )
        for(int j=0;j<LG[Coada[i]]; ++j)
             if(Sol[adiacent[Coada[i]][j]]==-1)
            {
                Coada[++L]=adiacent[Coada[i]][j];//elementul actual se adauga in varful cozii
                Sol[Coada[L]]=Sol[Coada[i]]+1;//solutia pentru elementul actual
            }
}

int main()
{
    Read();
    CreateLG();
    BFS();
    Print();

    f.close();
    g.close();
    return 0;
}