#include <bits/stdc++.h>
#define NMAX 100001

using namespace std;

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

int n, m, S, k;
vector <int> v[NMAX];

void unif()
{
    for(int i=1; i<=n; i++)
    {
        sort(v[i].begin(), v[i].end());
        v[i].resize(distance(v[i].begin(),unique(v[i].begin(), v[i].end())));
    }
}

int dis[NMAX];

void bfs(queue <int> q)
{
    while(!q.empty())
    {
        int x=q.front();
        //fout<<x<<" ";
        for(auto& j:v[x])
        {
            if(dis[j]==-1)
            {
                dis[j]=dis[x]+1;
                q.push(j);
            }
        }
        q.pop();
    }
}

int main()
{
    fin>>n>>m>>S;
    for(int i=1; i<=m; i++)
    {
        int a, b;
        fin>>a>>b;
        v[a].push_back(b);
    }
    for(int i=1; i<=n; i++) dis[i]=-1;
    unif();
    queue <int> q;
    q.push(S);
    dis[S]=0;
    bfs(q);
    for(int i=1; i<=n; i++)
    {
        fout<<dis[i]<<" ";
    }
}