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

using namespace std;

ifstream cin("bfs.in");
ofstream cout("bfs.out");

vector <vector <int> > a;
vector <int> d,q;
int n,s;

void read()
{
    int m,x,y;
    cin >> n >> m >> s;
    a.resize(n+1);
    d.resize(n+1);
    fill(d.begin(),d.end(),-1);
    for ( ; m ; m--)
    {
        cin >> x >> y;
        if (x!=y) a[x].push_back(y);
    }
    d[s]=0;
}

void solve()
{
    q.push_back(s);
    int x;
    for (int i=0; i<q.size(); i++)
    {
        for (int j=0; j<a[q[i]].size(); j++)
        {
            x=a[q[i]][j];
            if (d[x]==-1 || d[q[i]]+1<d[x])
            {
                q.push_back(a[q[i]][j]);
                d[x]=d[q[i]]+1;
            }
        }
    }
}

main()
{
    read();
    solve();
    copy(d.begin()+1,d.end(),ostream_iterator <int> (cout, " "));
}