#include<fstream>
#include<vector>
#include<list>
using namespace std;

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

int ls,ld,n,m,start,aux,i,a,b;
vector <list<int> > v(100010);
list <int> lista;
int cost[100010],coada[100010];
list <int> :: iterator itr;
int main()
{
    fin>>n>>m>>start;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b;
        v[a].push_back(b);
    }
    cost[start]=1;
    coada[ls=ld=1]=start;
    while(ls<=ld)
    {
        aux=coada[ls++];
        for(itr= v[aux].begin();itr!=v[aux].end();itr++)      // i=0;i<v[aux].size();++i
        {
            if(cost[*itr]==0)                                 //cost[v[aux][i]]==0
                {
                    cost[*itr]=cost[aux]+1;
                    coada[++ld]=*itr;
                }
        }
    }
    for(i=1;i<=n;++i)
    fout<<cost[i]-1<<" ";





return 0;
}