#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stdio.h>

#define INF 0x7fffffff
#define NMAX 50002

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Nod {
    int nod;
    int distanta;
	bool operator<(const Nod &o) const
	{
		return distanta > o.distanta;
	}

};
vector < vector < int > > G(NMAX);
vector < int > dist(NMAX, 0);
vector < bool > vizitat(NMAX);
vector < int > cnt_nod_inQ(NMAX, 0);
int n, m, s;

bool compare (const Nod& a, const Nod& b) {
    return a.distanta < b.distanta;
}

void read() {
	FILE * pFile;

	pFile = fopen("bfs.in", "r");
    //f >> n >> m;
	fscanf(pFile, "%d %d %d", &n, &m, &s);
	int x = 0, y = 0, dist = 0;
	Nod nod_pereche;
    while (m--) {
		fscanf(pFile, "%d %d", &x, &y);

		G[x].push_back(y);
    }
}
Nod constructNode(int nod, int distanta) {
	Nod new_node;
	new_node.nod = nod;
	new_node.distanta = distanta;
	return new_node;
}
void bfs() {
    queue<int> qNode;
    qNode.push(s);
    vizitat[s] = true;
    while (!qNode.empty()) {
        int nod = qNode.front();
        qNode.pop();
        for (int i = 0; i < G[nod].size(); i++) {
            int nodVecin = G[nod][i];
            if (!vizitat[nodVecin]) {
                vizitat[nodVecin] = true;
                dist[nodVecin] = dist[nod] + 1;
                qNode.push(nodVecin);
            }
        }
    }
    FILE * pFile;

	pFile = fopen("bfs.out", "w");
    for (int i = 1; i <= n; i++) {
        if (!dist[i] && i != s) {
            dist[i] = -1;
        }
        fprintf(pFile, "%d ", dist[i]);
    }
}
int main()
{
    read();
	bfs();
    return 0;
}