#include <cstring>
#include <fstream>
#include <queue>
using namespace std;

int main()
{
    vector<int>* Graph;
    int Noduri;
    int Muchii;
    int Sursa;

    ifstream in("bfs.in");
    in >> Noduri >> Muchii >> Sursa;
    Graph = new vector<int>[Noduri + 1];

    for (int i = 0, a, b; i != Muchii; ++i)
    {
        in >> a >> b;
        Graph[a].push_back(b);
    }
    in.close();

    int* Drum = new int[Noduri + 1];
    memset(Drum, -1, sizeof(int) * (Noduri + 1));

    queue<int> Nevizitate;
    Nevizitate.push(Sursa);
    Drum[Sursa] = 0;

    while (!Nevizitate.empty())
    {
        int current = Nevizitate.front();
        vector<int>::iterator st = Graph[current].begin();
        vector<int>::iterator end = Graph[current].end();

        for(st; st != end; ++st)
            if (Drum[*st] == -1)
            {
                Drum[*st] = Drum[current] + 1;
                Nevizitate.push(*st);
            }

        Nevizitate.pop();
    }

    ofstream out("bfs.out");
    for (int i = 1; i <= Noduri; ++i)
        out << Drum[i] << " ";
    out.close();

    delete[] Graph;
    delete[] Drum;

    return 0;
}