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

using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");

vector <int> graph[100005];
queue <int> myQueue;
/* myQueue.front() - primul el din coada
            .back() - ultimul
            .push_back(x); -adauga la finalul cozii
            .pop(); -sterge primul el
*/
int viz[100005], dist[100005], coada[100005];

int main ()
{
    int n, m, x, y, left, right, s;
    f>>n>>m>>s;
    for(int i=0; i<m; i++)
    {
        f>>x>>y;
        graph[x].push_back(y);
        // graph[y].push_back(x);
    }

    myQueue.push(s);
    dist[s] = 0;
    viz[s] = 1;

    while (!myQueue.empty()) //cat timp sunt elem in coada
    {
        int idx = myQueue.front();
        //g<<myQueue.front()<<" ";
        myQueue.pop();
        int dim = graph[idx].size();
        for(int i=0; i<dim; i++)
        {
            int vecin = graph[idx][i];
            if(!viz[vecin])
            {
                dist[vecin] = dist[idx] + 1;
                viz[vecin] = 1;
                myQueue.push(vecin);
            }
        }
    }
    for (int i=1; i<=n; i++)
    {
        if (dist[i] == 0 && i != s)
            dist[i] = -1;
        g<<dist[i]<<" ";
    }
    return 0;

    /*left = right = 1;
     coada[1] = s;
    while (left <= right) //cat timp sunt elem in coada
    {
        int idx = coada[left];
        int dim = graph[idx].size();
        for(int i=0; i<dim; i++)
        {
            int vecin = graph[idx][i];
            if(!viz[vecin])
            {
                dist[vecin] = dist[idx] + 1;
                viz[vecin] = 1;
                coada[++right] = vecin;
            }
        }
        left++;
    }
    for(int i=1; i<=n; i++)
        cout<<coada[i]<<" ";*/
}