#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)
{
    //vector<int>coada;
    int i,coada[nmax];
    int p,u,ic,sf;
    v[s-1]=0;
    ic=sf=0;
    coada[ic]=s;
    while(ic<=sf)
    {
        p=coada[ic];
        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, sf++, coada[sf]=lista[p][i];
        ic++;
    }

}
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();
}