#include <iostream>
#include <cstdio>
#include <vector>
#define buffs 1048576
using namespace std;
FILE*f=freopen("bfs.in","r",stdin);
char buff[buffs];
int pos=0,a,b,i,n,m,s,nrp=0,lg;
int c[100002],d[100002];
std::vector<int>v[100002];
inline void read ( int &nr)
{
nr=0;
while(buff[pos]<'0'||buff[pos]>'9') if(++pos==buffs)fread(buff,1,buffs,stdin),pos=0;
while(buff[pos]>='0'&&buff[pos]<='9')
{
    nr=(nr<<1)+(nr<<3)+buff[pos]-48;
    if(++pos==buffs)fread(buff,1,buffs,stdin),pos=0;
}
}
int main()
{fread(buff,1,buffs,stdin);
freopen("bfs.out","w",stdout);
    read(n);read(m);read(s);
for(i=1;i<=m;i++)
{
    read(a);read(b);
    v[a].push_back(b);
}
for(i=1;i<=n;i++)
    d[i]=-1;
nrp=0;
c[1]=s;
d[s]=0;
a=b=1;//prim ultim
while(a<=b)
{
    pos=c[a];nrp=d[pos];a++;
    lg=v[pos].size();
    for(i=0;i<lg;i++)
        if(!(d[v[pos][i]]>-1))
        {
            b++;
            c[b]=v[pos][i];
            d[v[pos][i]]=nrp+1;
        }
}
for(i=1;i<=n;i++)
   printf("%d ",d[i]);

}