#include <fstream>
#include <vector>

using namespace std;

vector <long int > a[100005];

long int n,m,s,i,x,y,sf1,sf,inc,nr,j,v[100005],poz[100005],viz[100005];
bool ok;

int main()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    f>>n>>m>>s;
    for (i=1;i<=m;i++) {
        f>>x>>y;
        a[x].push_back(y);
    }

    ok=true;
    sf=1;sf1=1;inc=1;v[1]=s;viz[s]=1;nr=0;
    while (ok==true) {
        ok=false;nr++;
        for (i=inc;i<=sf;i++)
            for (j=0;j<a[v[i]].size();j++)
            if (viz[a[v[i]][j]]==0) {ok=true;sf1++;viz[a[v[i]][j]]=1;v[sf1]=a[v[i]][j];poz[a[v[i]][j]]=nr;}
        inc=sf+1;
        sf=sf1;
    }

    for (i=1;i<=n;i++) {
    if (poz[i]==0 &&i!=s) g<<"-1"<<' ';
    else
    g<<poz[i]<<' ';
    }

    f.close();
    g.close();
    return 0;
}