#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define MAX_VERTICES 10000
using namespace std;

class Graph {
private:
    int V;
    int E;
    int startNode;
    vector<int>g[MAX_VERTICES+1];
public:
    int getStartNode() {
        return startNode;
    }

    void readGraph(string name_fin) {
        int x, y;
        ifstream fin(name_fin);
        fin >> V >> E >> startNode;
        for(int i = 0; i < E; ++i) {
            fin >> x >> y;
            g[x].push_back(y);
        }
        fin.close();
    }

    void BFS(int x) {
        vector<int> dist(MAX_VERTICES + 1, -1);
        queue<int> q;
        int node;
        ofstream fout("bfs.out");
        q.push(x);
        dist[x] = 0;
        while(!q.empty()) {
            node = q.front();
            q.pop();
            for(auto i : g[node]) {
                if(dist[i] == -1) {
                    dist[i] = 1 + dist[node];
                    q.push(i);
                }
            }
        }
        for(int i = 1; i <= V; ++i)
            fout << dist[i] << " ";
        fout << "\n";
        fout.close();
    }
};

int main() {
    Graph G;
    G.readGraph("bfs.in");
    G.BFS(G.getStartNode());
    return 0;
}