#include<cstdio>
#include<list>
#include<vector>
#include<algorithm>
#define nmax 100010
#define mmax 1000010
#define pb push_back
#define pf pop_front
using namespace std;
int n,m,s;
vector<int>lista[nmax];
vector<int>v;
void citire()
{
    int i,x,y;
    freopen("bfs.in","r",stdin);
    scanf("%d%d%d",&n,&m,&s );
    v.resize(n,-1);
    for(i=1;i<=m;++i)
      scanf("%d%d",&x,&y), lista[x].push_back(y);
}
void bfs(int s)
{
    list<int>coada;
    int i;
    coada.pb(s);
    v[s-1]=0;
    int p,u;
    while(!coada.empty())
    {
        p=coada.front();
        u=lista[p].size();
        for(i=0;i<u;++i)
          if(v[lista[p][i]-1]==-1)
           v[lista[p][i]-1]=v[p-1]+1, coada.pb(lista[p][i]);
        coada.pf();
    }

}
void afisare()
{
    freopen("bfs.out","w",stdout);
    vector<int>::iterator it;
    for(it=v.begin();it!=v.end();++it)
      printf("%d ",*it);

}
int main()
{
    citire();
    bfs(s);
    afisare();
}