#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int maxn=1e5+5;
vector<int> v[maxn];
int rsp[maxn];
bool viz[maxn];
int main()
{
    ifstream cin("bfs.in");
    ofstream cout("bfs.out");
    int n,m,st;
    cin>>n>>m>>st;
    for (int i=1;i<=n;i++)rsp[i]=1e9;
    for (int i=1;i<=m;i++) {
        int l,r;
        cin>>l>>r;
        v[l].push_back(r);
        //v[r].push_back(l);
    }
    rsp[st]=0;
    queue<int> q;
    q.push(st);
    while(!q.empty()) {
        int nod=q.front();
        q.pop();
        if (viz[nod])continue;
        //cout<<nod<<" "<<rsp[nod]<<endl;
        viz[nod]=true;
        for (auto elem:v[nod]) {
            rsp[elem]=min(rsp[elem],rsp[nod]+1);
            q.push(elem);
        }
    }
    for (int i=1;i<=n;i++) {
        if (rsp[i]==1e9) {
            cout<<"-1"<<" ";
        }else cout<<rsp[i]<<" ";
    }
    return 0;
}