#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
const int N=100001;
ifstream in("bfs.in");
ofstream out("bfs.out");
int n,m,s,a,b,x,cost[N];
bool visit[N];
vector<int> asd[N];
deque<int> coada;
int main()
{
    in>>n>>m>>s;
    for (int i=1;i<=m;i++)
    {
        in>>a>>b;
        asd[a].push_back(b);
        //cout<<asd[a].at(asd[a].size()-1)<<" ";
    }
    for (int i=0;i<=n;i++) cost[i]=-1;
    cost[s]=0;
    coada.push_back(s);
    /*for (int i=0;i<=n;i++)
    {
        cout<<i<<". ";
        for (int j=1;j<asd[i].size();j++)
            cout<<asd[i].at(j)<<" ";
        cout<<"\n";
    }*/
    while(coada.size())
    {
        x=coada.at(0); //cout<<x<<" "<<asd[x].size()<<"\n";
        visit[x]=true;
        for (int i=0;i<asd[x].size();i++)
        {
            if (!visit[asd[x].at(i)])
            {
                coada.push_back(asd[x].at(i));
                cost[asd[x].at(i)]=cost[x]+1;
            }
        }
        coada.pop_front();
    }
    for (int i=1;i<=n;i++)
        out<<cost[i]<<" ";
    return 0;
}