#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

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

const int NMAX = 1e6+1;

vector <int> graf[NMAX];
queue <int> Q;
int used[NMAX+1];
int sol[NMAX];
int n,m,s;
void read()
{

    in>>n>>m>>s;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        in>>x>>y;
        graf[x].push_back(y);
    }
    Q.push(s);
    used[s]=1;
    sol[s]=1;
}
void bfs()
{
    while(Q.empty()==0)
    {
        int x=Q.front();
        while(graf[x].empty()==0)
        {
            if(used[graf[x].back()]==0)
            {
                Q.push(graf[x].back());
                used[graf[x].back()]=1;
                sol[graf[x].back()]=sol[x]+1;
            }
            graf[x].pop_back();
        }
        Q.pop();
    }
}
void print()
{
    for(int i=1; i<=n; i++)
        out<<sol[i]-1<<" ";
}
int main()
{
    read();
    bfs();
    print();
}