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

using namespace std;

const int NMAX = 1e5;

ifstream cin("bfs.in");
ofstream cout("bfs.out");

vector<vector<int>> edges;
vector<int> viz;
int n, m, s;

void read()
{
    edges.resize(n);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;

        edges[a - 1].push_back(b - 1);
    }
}

void print()
{
    for (int i = 0; i < edges.size(); i++)
    {
        //ut << i + 1 << " : ";
        for (int j = 0; j < edges[i].size(); j++)
        {
            cout << edges[i][j] << ' ';
        }
        cout << '\n';
    }
}

void dfs(int node)
{
    viz[node] = 1;

    for (auto next : edges[node])
    {
        if (viz[next] == 0)
        {
            //cout << node + 1 << " -> " << next + 1 << '\n';
            dfs(next);
        }
    }
}

void bfs(int node)
{
    viz.resize(n, -1);

    queue<int> q;

    viz[node] = 0;
    q.push(node);

    while (!q.empty())
    {
        node = q.front();
        for (auto next : edges[node])
        {
            if (viz[next] == -1)
            {
                q.push(next);
                viz[next] = viz[node] + 1;
            }
        }
        q.pop();
    }
}

int main()
{

    cin >> n >> m >> s;
    read();

    bfs(s - 1);
    for (int i = 0; i < edges.size(); i++)
    {
        cout << viz[i] << ' ';
    }
    return 0;
}