#include <iostream>
#include <fstream>
#include <deque>
#include <list>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");

int* BFS(list<int> *v,int start,int n)
{
    int *a=new int[n],*viz=new int[n],i=1,aux;
    for(i=0;i<n;i++)
        viz[i]=0;
    deque<int> c;
    for(i=0;i<n;i++)
        a[i]=-1;
    a[start]=0;
    c.push_back(start);
    viz[start]=1;
    i=1;
    while(!c.empty())
    {
        aux=c.front();
        list<int>::iterator it;
        for(it=v[aux].begin();it!=v[aux].end();it++)
            if(viz[*it]==0)
                {
                    c.push_back(*it);
                    a[*it]=a[aux]+1;
                    viz[*it]=1;
                }
        i++;
        c.pop_front();
    }
    return a;
}

int main()
{
    int n,m,s,i,x,y,*a;
    list<int> *v;
    in>>n>>m>>s;
    v=new list<int>[n];
    for(i=0;i<m;i++)
    {
        in>>x>>y;
        v[x-1].push_back(y-1);
    }
    a=BFS(v,s-1,n);
    for(i=0;i<n;i++)
        out<<a[i]<<" ";
    return 0;
}