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

using namespace std;

vector <int>l[100005];

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

int n,m,r,i,x,y,st,dr,vec,c[100005],v[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;
}