#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int n,m,s,i,j,x,y,q[100001],d[100001],st,dr,nrq;
vector<int> a[100001];

int main()
{
    f>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x].push_back(y);
    }
    for(i=1;i<=n;i++) d[i]=-1;
    st=1; dr=1; q[dr]=s; d[s]=0;
    while(st<=dr)
    {
        x=q[st];
        for(j=0;j<a[x].size();j++)
        {
            if(d[a[x][j]]<0 || d[a[x][j]]>d[x]+1)
            {
                q[++dr]=a[x][j];
                d[a[x][j]]=d[x]+1;
            }
        }
        st++;
    }
    for(i=1;i<=n;i++) g<<d[i]<<' ';
    return 0;
}