#include <bits/stdc++.h>

#define Nmax 100001

using namespace std;

vector <int> adj[Nmax];
int q[Nmax],viz[Nmax];
int d[Nmax],s,n,m;

void bfs(int nod)
{
    int st=1,dr=1;
    q[1] = s;
    d[s] = 1;
    while(dr-st+1>0)
    {
        nod = q[st];
        st++;
        for(int i = 0; i < adj[nod].size(); i++)
        {
            if(d[adj[nod][i]] == 0 || d[adj[nod][i]]>d[nod]+1)
            {
                d[adj[nod][i]]=d[nod]+1;
                dr++;
                q[dr]=adj[nod][i];
            }
        }
    }
}


int main()
{
    ifstream fin ("bfs.in");
    ofstream fout ("bfs.out");
    fin>>n>>m>>s;
    for (int i=0; i<m; ++i)
    {
        int a,b;
        fin>>a>>b;
        adj[a].push_back(b);
    }
    bfs(s);
    for (int i=1; i<=n; ++i)
    {
        fout<<d[i]-1<<" ";
    }
}