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

std::ifstream fin("bfs.in");
std::ofstream fout("bfs.out");
std::vector<std::vector<int>> ad;
std::vector<int> cost(1, -1);

void ConstructieListaAdiacentaNeorientat(int &m)
{
    int i, j;
    for (int k = 1; k <= m; k++)
    {
        fin >> i;
        fin >> j;
        ad[i].push_back(j);
        ad[j].push_back(i);
    }
    std::cout << "Vectorul a fost construit\n";
}

void BFS(int start)
{
    std::queue<int> q;
    std::vector<bool> visited(ad.size(), false);

    q.push(start);
    visited[start] = true;
    while (!q.empty())
    {
        int nod_curent = q.front();
        q.pop();
        std::cout << nod_curent << " ";
        for (int i : ad[nod_curent])
        {
            if (!visited[i])
            {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

void AfisareLista(int n)
{
    for (int i = 1; i <= n; i++)
    {
        std::cout << i << ": ";
        for (auto j : ad[i])
            std::cout << j << " ";
        std::cout << "\n";
    }
}

void ConstructieListaAdiacentaOrientat(int &m)
{
    int i, j;
    for (int k = 1; k <= m; k++)
    {
        fin >> i;
        fin >> j;
        ad[i].push_back(j);
    }
    std::cout << "Vectorul a fost construit\n";
}

void minimarce(int start)
{
    std::queue<int> q;
    std::vector<bool> visited(ad.size(), false);

    q.push(start);
    visited[start] = true;
    cost[start - 1] = 0;
    while (!q.empty())
    {
        int nod_curent = q.front();
        q.pop();
        for (int i : ad[nod_curent])
        {
            if (!visited[i])
            {
                visited[i] = true;
                q.push(i);
                cost[i - 1] = cost[nod_curent - 1] + 1;
            }
        }
    }
    for (auto it : cost)
        fout << it << " ";
}
int main()
{
    int n, m, s;
    fin >> n >> m >> s;
    ad.resize(n + 1);
    cost.resize(n, -1);
    ConstructieListaAdiacentaOrientat(m);
    AfisareLista(n);
    minimarce(s);
    return 0;
}