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

int main(){
int n,m,s,x,y;
vector<int> v[100001];
ifstream fin("bfs.in");
ofstream fout("bfs.out");
fin>>n>>m>>s;
for( ;m>0;--m){
	fin>>x>>y;
	v[x].push_back(y);
}
fin.close();

vector<int> d(n+1,-1);
queue<int> q;
q.push(s);
d[s]=0;
vector<int>::iterator it;

while(!q.empty()){
	s=q.front();
	q.pop();
	for(it=v[s].begin();it!=v[s].end();++it)
		if(d[*it]<0){
			d[*it]=d[s]+1;
			q.push(*it);
		}
	}
for(it=d.begin()+1;it!=d.end();++it)
	fout<<*it<<' ';
return 0;
}