#include <fstream>
#include <vector>
#include <iterator>

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

vector<int> graf[100000];

int n,m,s,rsp[100001];

void BFS(int nod){

    int queue[100000], st=0, fn=0,level=1;
    ++fn;
    queue[fn] = nod;
    rsp[nod] = 1;
    while(st<fn){
        ++st;
        nod = queue[st];
        vector<int>::iterator ptr;
        for(ptr = graf[nod].begin();ptr<graf[nod].end();++ptr){
                if(rsp[*ptr]==0){

                    rsp[*ptr] = rsp[nod] + 1;
                    ++fn;
                    queue[fn] = *ptr;

                }
                else rsp[*ptr] = min(rsp[*ptr], rsp[nod]+1);

        }

    }

}

int main(){
    fin>>n>>m>>s;
    for(int i=0;i<=m;++i){
        int a,b;
        fin>>a>>b;
        graf[a].push_back(b);
    }
    BFS(s);

    for(int i=1;i<=n;++i)
        fout<<rsp[i]<<' ';

    return 0;
}