#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005

using namespace std;

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

vector <int> L[nmax];
int n,m,s;
int d[nmax]; // vector in care retin distantele
int nr[nmax],q[nmax];
int k; // lungimea cozii
void Citire()
{

    int i ,x,y;
    fin>>n>>m>>s;
    for(i=1;i<=m;i++)
     {
         fin>>x>>y;
         L[x].push_back(y);
     }
    for(i=1;i<=n;i++)
      nr[i]=L[i].size();

     fin.close();
}

void Init()
{
    for(int i=0;i<=nmax;i++)
     d[i]=-1;
}


int main()
{
    Citire();

    int i,j;
    Init();
    q[1] = s;
    d[s]=0;
    k=1;

    for(i=1;i<=k;i++)
        for(j = 0; j < nr[q[i]]; j++)
            if(d[L[q[i]][j]]==-1)
            {
                q[++k] = L[q[i]][j];
                d[q[k]] = d[q[i]] + 1;
            }

    for(i=1;i<=n;i++)
        fout << d[i]<<' ';



    return 0;
}