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

void bfs(int S, vector<int> adjList[], int costToS[])
{
    queue<int> q;
    q.push(S);

    int x;
    costToS[S] = 0;
    while (!q.empty())
    {
        x = q.front(), q.pop();
        for (int i = 0; i < adjList[x].size(); i++)
        {
            int neighbor = adjList[x][i];
            if (costToS[neighbor] == -1)
            {
                q.push(neighbor);
                costToS[neighbor] = costToS[x] + 1;
            }
        }
    }
}

int main()
{
    int N, M, S;
    ifstream f("bfs.in");
    f >> N >> M >> S;
    vector<int> adjList[N + 1];
    int x, y;
    for (int i = 0; i < M; i++)
    {
        f >> x >> y;
        adjList[x].push_back(y);
    }
    f.close();

    int costToS[N + 1];
    fill(costToS + 1, costToS + (N + 1), -1);
    bfs(S, adjList, costToS);
    ofstream g("bfs.out");
    for (int i = 1; i <= N; i++)
        g << costToS[i] << " ";
    g.close();
    return 0;
}