#include <bits/stdc++.h>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
const int nmax=100001;
int n,muchii,start;
vector<int>L[nmax];
///Complexitate O(n+m)
int dist[nmax],c[nmax];
bool viz[nmax];
int main()
{
    int st,dr;
    st=dr=1;
    fin>>n>>muchii>>start;
    for(int i=1;i<=muchii;i++)
    {
        int x,y;
        fin>>x>>y;
        L[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        dist[i]=-1;
    c[st]=c[dr]=start;
    viz[start]=true;
    dist[start]=0;
    while(st<=dr)
    {
        int x=c[st];
        ++st;
        for(int i=0;i<L[x].size();i++)
            if(!viz[L[x][i]])
            {
                ++dr;
                c[dr]=L[x][i];
                dist[L[x][i]]=dist[x]+1;
                viz[L[x][i]]=true;
            }
    }
    for(int i=1;i<=n;i++)
        fout<<dist[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}