#include <iostream>
#include <fstream>

using namespace std;

int prez[100001],v[100001],con[1000001][2],s,n,m,i,j,k;

fstream f,g;

int main()
{
    f.open("bfs.in",ios_base::in);
    g.open("bfs.out",ios_base::out);
    f>>n>>m>>s;
    for(i=0;i<n;i++)prez[i]=-1;
    for(i=0;i<m;i++)
    {
        f>>con[i][0]>>con[i][1];
        con[i][0]--;
        con[i][1]--;
    }
    prez[s-1]=0;
    v[0]=s-1;
    i=0;
    j=1;
    while(i!=j)
    {
        for(k=0;k<m;k++)if(con[k][0]==v[i]&&prez[con[k][1]]==-1)
        {
            prez[con[k][1]]=prez[v[i]]+1;
            v[j]=con[k][1];
            j++;
        }
        i++;
    }
    for(i=0;i<n;i++)g<<prez[i]<<' ';
}