#include <bits/stdc++.h>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int const N=(int)1e5+5;
int rez[N];
int n,m,s;
bool viz[N];
vector <int> v[N];
queue <int> q;
void af()
{
    cout<<q.size()<<':'<<q.front()<<' '<<q.back()<<'\n';
}
int main()
{
    fin>>n>>m>>s;
    int x,y;
    while(m--)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }
    q.push(s);
    rez[s]=1;
    viz[s]=true;
    for(int i=2;q.size();i++)
    {

        while(rez[q.front()]==i-1)
        {
            vector <int>::iterator it;
            for(it=v[q.front()].begin();it!=v[q.front()].end();it++)
                if(!viz[*it])
            {
                viz[*it]=true;
                q.push(*it);
                rez[*it]=i;
            }
            q.pop();

        }
    }
    for(int i=1;i<=n;i++)
        fout<<rez[i]-1<<' ';
}