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

class Graph {
private:
    int V, E, source;
    int dist[MAX_VERTICES+1];
    vector<int>g[MAX_VERTICES+1];
public:
    void readGraph(char name_fin[30]) {
        int n, m, i, x, y;
        ifstream fin(name_fin);
        fin >> n >> m >> x;
        V = n;
        E = m;
        source = x;
        for(i = 0; i < E; i++) {
            fin >> x >> y;
            g[x].push_back(y);
        }
        fin.close();
    }
    void BFS(int x) {
        int node;
        queue<int>q;
        for(int i = 1; i <= V; i++)
            dist[i] = -1;
        dist[x] = 0;
        q.push(x);
        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);
                }
            }
        }
    }
    void printDistances(char name_fout[30]) {
        ofstream fout(name_fout);
        for(int i = 1; i <= V; i++)
            fout << dist[i] << " ";
        fout << "\n";
        fout.close();
    }
    int getSource() {
        return source;
    }
};

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