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

vector<int> graf[100001];
bool vizitat[100001];

void dfs(int k){
  	vizitat[k] = true;
    cout<<k<<' '; //facem ceva op

  	for (int vecin : graf[k]){
      	if (!vizitat[vecin]){
          	dfs(vecin);
        }
    }
}

#include <queue>

int rang[100001];

void bfs(int start){
    queue<int> q;

    q.push(start);
    vizitat[start] = true;
    while(!q.empty()){
        int nod = q.front();
        for (int vecin : graf[nod]){
            if (!vizitat[vecin]){
                //cout<<vecin;//operatii
                vizitat[vecin] = true;
                rang[vecin] = rang[nod] + 1;
                q.push(vecin);
            }
        }
        q.pop();
    }
}

int main(){
	int v/*vertices*/, e; //edge
  	ifstream fin("bfs.in");
  	ofstream fout("bfs.out");
  	int start;
  	fin>>v>>e>>start;
  	int a,b;
  	for (int i=0; i<e; ++i){
      	fin>>a>>b;
      	graf[a].push_back(b);
      	//graf[b].push_back(a);
    }
  	bfs(start);
    for (int i=1; i<=v; ++i){
        /*
        if (rang[i]==0 && i!=start)
            cout<<"-1 ";
        else cout<<rang[i]<<' ';
        */
        if (vizitat[i]==false)
            fout<<"-1 ";
        else fout<<rang[i]<<' ';
    }
}