#include<fstream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
ifstream f ("bfs.in");
ofstream g ("bfs.out");
int n,m,s,t[1000010],x,y;
vector<int>G[1000010];
queue<int>q;
int main()
{
    f>>n>>m>>s;
    q.push(s);
    for(int i=1;i<=m;++i){
        f>>x>>y;
        G[x].push_back(y);
    }
     for(int i=1;i<=n;++i){
        t[i]=1000000000;
    }

    t[s]=0;
    while(!q.empty()){
        x=q.front();
        q.pop();
        for(int i=0;i<G[x].size();++i){
            if(t[G[x][i]]>t[x]+1){
                t[G[x][i]]=t[x]+1;
                q.push(G[x][i]);
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(t[i]==1000000000) g<<-1<<" ";
        else g<<t[i]<<" ";
    }
}