#include <iostream>
#include <bits/stdc++.h>

using namespace std;

class graph
{
    // bitul 1 orientat sau neorientat, bitul 2 cost muchie
    enum input {orientat = 0, neorientat = 1, cu_cost = 2};
    struct muchie
    {
        int from, to, cost;
        muchie(int _from, int _to, int _cost = 1):
            from(_from), to(_to), cost(_cost)
            {

            }
    };
    int n,m;
    int* extraArgs = nullptr;
    vector<pair<int,int>>* la = nullptr;
    int* dist = nullptr;
    int* ids = nullptr;
    int* lowLink = nullptr;
    vector<int**> vecsUsed;

    ifstream f;
    ofstream g;
public:
    void readData(string nume_fisier, input _tip_graf, int _extra_args_count, vector<pair<int**, int>> initVecs);
    void cleanup();

    void bfs();
};

void graph::readData (string nume_fisier, input _tip_graf, int _extra_args_count, vector<pair<int**, int>> initVecs)
{
    f.open(nume_fisier);
    f >> n >> m;
    la = new vector<pair<int,int>>[n+1];
    for (auto& per: initVecs)
    {
        vecsUsed.push_back(per.first);

        int** p = per.first;
        int val = per.second;
        *p = new int[n+1];
        for (int i = 1; i <= n; i++)
            (*p)[i] = val;
    }
    if (_extra_args_count)
    {
        extraArgs = new int[_extra_args_count];
        for (int i = 0; i < _extra_args_count; i++)
            f >> extraArgs[i];
    }

    for (int i = 1; i <= m; i++)
    {
        int x,y,c;
        f >> x >> y;
        if (_tip_graf & input::cu_cost)
            f >> c;
        la[x].push_back({y,c});
        if (_tip_graf & input::neorientat)
            la[y].push_back({x,c});
    }

    f.close();
}

void graph::bfs()
{
    ofstream g("bfs.out");
    readData("bfs.in", input::orientat, 1, {{&dist, -1}});

    int start = extraArgs[0];

    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (q.size())
    {
        for (auto to: la[q.front()])
        {
            if (dist[to.first] == -1)
            {
                q.push(to.first);
                dist[to.first] = dist[q.front()] + 1;
            }
        }
        q.pop();
    }

    for (int i = 1; i <= n; i++)
        g << dist[i] << ' ';

    delete[] la;
    delete[] extraArgs;
    delete[] dist;
}

int main()
{
    graph g;
    g.bfs();

    return 0;
}