#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector <int>l[100005];
int i,n,m,x,y,nr,vec,r,st,dr,v[100005],c[100005];

int main()
{
    fin >> n >> m >> r;
    for (i=1;i<=m;i++)
    {
        fin >> x >> y;
        l[x].push_back(y);
    }
    for (i=1;i<=n;i++) sort(l[i].begin(),l[i].end());
    st=1;
    dr=1;
    c[st]=r;
    v[r]=1;
    while (st<=dr)
    {
        for (i=0;i<l[c[st]].size();i++)
        {
            vec=l[c[st]][i];
            if (v[vec]==0)
            {
                v[vec]=v[c[st]]+1;
                dr++;
                c[dr]=vec;
            }
        }
        st++;
    }
    for (i=1;i<=n;i++) fout << v[i]-1 << " ";

    return 0;
}