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

struct node{
int x, y, cost;
};

class Graph{

int V;
int m;
list<node>*Adj;

public:Graph(int v, int m){
this->V=v;
Adj=new list<node>[v];
this->m=m;
}

public:addEdge(int x, int y){
Adj[x].push_back({x, y, 0});
}

public:bfs(int s){

int c;
list<node>::iterator i;
vector<int>cost(this->V, -1);
list<int>q;
q.push_back(s);
cost[s]=0;

while(!q.empty()){
c=q.front();
q.pop_front();

for(i=Adj[c].begin();i!=Adj[c].end();i++){
if(cost[(*i).y]==-1){
q.push_back((*i).y);
cost[(*i).y]=cost[c]+1;
}
}

}

for(int i=1;i<=this->m;i++){
o<<cost[i]<<" ";
}

}

};

int main(){
int n, m, s, x, y;
f>>n>>m>>s;

Graph g(m, n);

for(int i=0;i<m;i++){
f>>x>>y;
g.addEdge(x, y);
}

g.bfs(s);

}