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

int N, M, S, x, y, crt;
vector<vector<int>> lista;
vector<int> coada;
vector<int> cost;

int main() {
    ifstream input("bfs.in");

    input >> N >> M >> S;
    coada.insert(coada.begin(), S);
    for (int i = 0; i < N; i++) {
        cost.push_back(-1);
    }
    cost[S - 1] = 0;

    for (int i = 0; i < M; i++) {
        input >> x >> y;
        lista[x - 1].push_back(y);
    }

    input.close();

    for (int i = 0; i < N; i++) {
        crt = coada[0];
        coada.pop_back();
        
        for (int vecin: lista[crt - 1]) {
            coada.push_back(vecin);
            cost[vecin - 1] = cost[crt - 1] + 1;
        }
    }

    ofstream output("bfs.out");
    
    for (int i = 0; i < N; i++) {
        output << cost[i];
    }

    output.close();

    return 0;
}