#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
 
ifstream fin("bfs.in");
ofstream fout("bfs.out");
 
const int NLIM = 100005;
 
int peaks, arrows, startPeak;
int Distanta[NLIM];
vector <int> Graf[NLIM];
queue <int> Coada;
 
void BFS() {
    int Nod, Vecin;
    while (!Coada.empty()) {
        Nod = Coada.front();
        for (unsigned i = 0; i < Graf[Nod].size(); ++i) {
            Vecin = Graf[Nod][i];
            if (Distanta[Vecin] == -1) {
                Coada.push(Vecin);
                Distanta[Vecin] = Distanta[Nod] + 1;
            }
        }
        Coada.pop();
    }
}
 
void Citire() {
    fin >> peaks >> arrows >> startPeak;
    int x,y;
    for (int i = 1; i <= arrows; ++i) {
        fin >> x >> y;
        Graf[x].push_back(y);
    }
    for (int i = 1; i <= peaks; ++i) {
        Distanta[i] = -1;
    }
    Distanta[startPeak] = 0;
}
 
int main() {
    Citire();
    Coada.push(startPeak);
    BFS();
    for (int i = 1; i <= peaks; ++i) {
        fout << Distanta[i] << " ";
    }
    return 0;
}

/*

 
 Teste:
 exemplu:
 5 7 2
 1 2
 2 1
 2 2
 3 2
 2 5
 5 3
 4 5
 
 -> 1 0 2 -1 1 NU
 
 5 4 1
 1 2
 2 3
 3 5
 5 4
 
 -> 0 1 2 4 3
 
 5 3 1
 1 2
 2 3
 3 5
 
 -> 0 1 2 -1 3
 
 
 5 1 1
 1 2
 
 -> 0 1 -1 -1 -1
 
 5 20 3
 1 2
 1 3
 1 4
 1 5
 2 1
 2 3
 2 4
 2 5
 3 1
 3 2
 3 4
 3 5
 4 1
 4 2
 4 3
 4 5
 5 1
 5 2
 5 3
 5 4
 
 -> 1 1 0 1 1
 
 5 5 2
 2 3
 2 1
 4 1
 3 4
 1 5
 
 -> 1 0 1 2 3 GRESIT (2 -> 5) trebuia sa dea 2
 
 */