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

using namespace std;

struct Nod {
    int n = -1;
    vector<int> Adj;
};

struct Graph {
    bool Unoriented;
    vector<Nod> Nodes;
    int edgeCount = 0;

    Graph(bool _Unoriented = false) {
        Unoriented = _Unoriented;
    }


    void SetNodeCount(int n) {
        Nodes.resize(n);
        for (int i = 0; i < n; i++) {
            Nodes[i].n = i;
        }
    }

    int GetNodeCount() {
        return Nodes.size();
    }

    Nod& operator[] (int i) {
        return Nodes[i];
    }

    void AddEdge(int u, int v) {
        Nodes[u].Adj.push_back(v);
        if (Unoriented)
            Nodes[v].Adj.push_back(u);
        edgeCount++;
    }

    int GetEdgeCount() const {
        return edgeCount;
    }
};

vector<int> bfs(Graph &G, int S) {
    vector<int> res(G.GetNodeCount(), -1);

    queue<int> Q;
    Q.push(S);
    res[S] = 0;

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();

        for (int i : G[u].Adj) {
            if (res[i] == -1) {
                Q.push(i);
                res[i] = res[u] + 1;
            }
        }
    }

    return res;
}

int dfs(Graph &G) {
    vector<bool> vis(G.GetNodeCount(), false);
    stack<int> S;

    int n = 0;

    for (int i = 0; i < G.GetNodeCount(); i++) {
        if (vis[i]) {
            continue;
        }

        S.push(i);
        vis[i] = true;
        n++;
        while (!S.empty()) {
            int u = S.top();
            S.pop();

            for (int i : G[u].Adj) {
                if (!vis[i]) {
                    S.push(i);
                    vis[i] = true;
                }
            }
        }
    }

    return n;
}

pair<int, int> grarb(Graph &G) {
    int AddCount = -1;
    int RemoveCount = 0;

    int M = G.GetEdgeCount() / 2;
    int N = G.GetNodeCount();
    int C = dfs(G);
    RemoveCount = M - N + C;
    AddCount = C - 1;

    return make_pair(RemoveCount, AddCount);
}

vector<int> berarii2(Graph &G, vector<int> &B) {
    vector<bool> vis(G.GetNodeCount(), false);

    queue<int> Q;

    for (auto b : B) {
        Q.push(b);
        vis[b] = true;

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int i : G[u].Adj) {
                if (!vis[i]) {
                    Q.push(i);
                    vis[i] = true;
                }
            }
        }
    }

    vector<int> res;
    for (int i = 0; i < G.GetNodeCount(); i++) {
        if (!vis[i]) {
            res.push_back(i);
        }
    }

    return res;
}

#define in fin
#define out fout

ifstream fin("bfs.in");
ofstream fout("bfs.out");

void ReadMEdges(Graph &G, int M) {
    while (M--) {
        int u, v;
        in >> u >> v;
        G.AddEdge(u-1, v-1);
    }
}

void ReadGraph(Graph &G, int N, int M) {
    G.SetNodeCount(N);
    ReadMEdges(G, M);
}



int main() {
    Graph G;
    int N, M;
    in >> N >> M;

    // Pre Graph Read
    int S;
    in >> S;
    //...

    ReadGraph(G, N, M);


    // Output
    auto k = bfs(G, S-1);
    for (auto i : k) {
        cout << i << " ";
    }
    //...
}