/// BFS
#include<fstream>
#include<vector>
#include<list>
#include<queue>

using namespace std;

int main() {
    ifstream inStr("bfs.in");
    ofstream outStr("bfs.out");

    unsigned numNodes, numArcs, S;
    inStr >> numNodes >> numArcs >> S; S--;
    vector<list<unsigned> > adjList(numNodes);

    unsigned from, to;
    for(unsigned i=0; i<numArcs; i++) {
        inStr >> from >> to;
        adjList[from-1].push_back(to-1);
    }

    queue<unsigned> q;
    vector<long> dist(numNodes, -1);
    vector<bool> seen(numNodes, false);
    list<unsigned>::iterator it;
    dist[S]=0;
    q.push(S);

    while(!q.empty()) {
        seen[q.front()]=true;
        for(it=adjList[q.front()].begin(); it!=adjList[q.front()].end(); it++)
            if(!seen[*it]) {
                q.push(*it);
                if(dist[q.front()]+1<dist[*it] || dist[*it]==-1)
                    dist[*it]=dist[q.front()]+1;
           }

        q.pop();
    }

    for(unsigned i=0; i<numNodes; i++)
        outStr << dist[i] << ' ';

    return 0;
}