#include<fstream>
#include<vector>
#include<queue>
using namespace std;


class Graph{

private:

    vector< vector<int> > V;

public:
    void build (int size) {
        vector<int> emptyVector;
        V.assign( size, emptyVector );
    }

    void edge(int x, int y) {
        V[x].push_back(y);
    }

    vector<int> bfs(int root) {
        vector<int> rez(V.size(), -1);
        queue<int> Q;

        Q.push(root);
        rez[root]=0;
        while(!Q.empty()) {
            for(vector<int>::iterator it = V[Q.front()].begin(); it != V[Q.front()].end(); it++) {
                if(rez[*it]==-1) {
                    Q.push(*it);
                    rez[*it]=rez[Q.front()]+1;
                }
            }
            Q.pop();
        }
        return rez;
    }

};

int main() {
    ifstream fin; fin.open("bfs.in");

    Graph G;
    int n,m,nod;
    fin>>n>>m>>nod;
    G.build(n);


    int x,y;
    while(m--) {
        fin>>x>>y;
        G.edge(x-1,y-1);
    }

    fin.close();

    vector<int> R = G.bfs(nod-1);


    ofstream fout; fout.open("bfs.out");
    for(vector<int>::iterator it = R.begin(); it<R.end()-1; it++)
        fout<<(*it)<<' ';
    fout<<R.back()<<'\n';
    fout.close();
    return 0;
}