#include<bits/stdc++.h>
using namespace std;
ifstream F("bfs.in");
ofstream G("bfs.out");
#define Z 2048
int m,n,i,j,k,p=Z,q,b[100001],c[100001],d[6];
vector<int> a[100001];
char s[Z],t[Z];
inline char A()
{
    if(p==Z)
        F.read(s,Z),p=0;
    return s[p++];
}
int B()
{
    char c;
    int n=0;
    for(c=A();isdigit(c);n=n*10+c-48,c=A());
    return n;
}
inline void C()
{
    if(q==Z)
        G.write(t,Z),q=0;
}
int main()
{
    for(n=B(),m=B(),k=B();m--;i=B(),j=B(),a[i].push_back(j));
    for(b[k]=1,c[++c[0]]=k,i=1;i<=c[0];++i)
        for(int j:a[c[i]])
            if(!b[j])
                b[j]=b[c[i]]+1,c[++c[0]]=j;
    for(i=1;i<=n;t[q++]=' ',C(),++i)
        if(j=b[i]-1,j<0)
            t[q++]='-',C(),t[q++]=49,C();
        else {
            for(k=0,d[k++]=j%10,j/=10;j;d[k++]=j%10,j/=10);
            for(;k;t[q++]=d[--k]+48,C());
        }
    return G.write(t,q),0;
}