#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

vector <int> graf[100000 + 5];
vector <int> viz;
queue <int> coada;
vector <int> cost;

void bfs()
{
    //cat timp coada nu e goala
    while(!coada.empty())
    {
        int x = coada.front();
        viz[x] = 1;
        cout << "x = " << x << ' ';
        //il sterg din coada
        coada.pop();
        int lg = graf[x].size();

        //parcurg toti vecinii si ii adaug in coada
        for(int i = 0; i < lg; ++i)
        {
            if(viz[graf[x][i]] == 0)
            {
                coada.push(graf[x][i]);
                cost[graf[x][i]] = cost[x] + 1;
            }
        }
    }
}

int main()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");

    int n, m, s;
    f >> n >> m >> s;
    //citesc datele
    for(int i = 0; i < m; ++i)
    {
        int a, b;
        f >> a >> b;
        graf[a].push_back(b);
    }

    //setare dimensiuni vectori
    viz.resize(n+1);
    cost.resize(n+2);
    for(int i = 1; i <= n; ++i)
        cost[i] = -1;

    cost[s] = 0;

    coada.push(s);
    bfs();

    //afisez vectorul de costuri
    for(int i = 1; i <= n; ++i)
        g << cost[i] << ' ';

    f.close();
    g.close();

    return 0;
}