#include <bits/stdc++.h>
using namespace std;

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

#define cin in
#define cout out
#define pb push_back
#define f first
#define s second
#define FOR(i, a, b) for(int i = a; i <= b; ++i)

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;

const ll INF = 1e6;
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
const ll nmax = 1e5;

ll n, m, x, y, z, i, j, k, l, r, p;
ll v[nmax + 1];
//ll a[nmax + 1];
//ll b[nmax + 1];
ll ans = 0, cnt = 0, maxim;
string s, t;
vector <int> edges[nmax + 1];
queue <int> q;

void BFS(){
	int node;
	while(!q.empty()){
		node = q.front();
		q.pop();
		FOR(i, 0, edges[node].size() - 1){
			int nb = edges[node][i];
			if(v[nb] == -1){
				q.push(nb);
				v[nb] = v[node] + 1;
			}
		}
	}
}

void solve(int tc = 0){
	cin >> n >> m >> p;
	while(m--){
		cin >> x >> y;
		edges[x].pb(y);
	}
	memset(v, -1, sizeof(v));
	v[p] = 0;
	q.push(p);
	BFS();
	FOR(i, 1, n)
		cout << v[i] << " ";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	//cin >> tc;
	FOR(i, 1, tc)
		solve(i);
}