#include <iostream>
#include <vector>
#include<queue>
#include<fstream>
using namespace std;
int n, m, s;
vector<vector <int> > graph;
vector<int> visited;
struct info
{
    int d,elem;
};
void bfs (int vertex)
{
    if(vertex<0||vertex>n-1)
        return;
    queue <info> q;
    info element;
    info aux;
    aux.d=0;
    aux.elem=vertex;
    q.push(aux);
    visited[vertex]=0;
    while(!q.empty())
    {
        element=q.front();
        for(int i=0;i<graph[element.elem].size();i++)
        {
            if(visited[graph[element.elem][i]]==-1)
            {
                aux.d=1+element.d;
                aux.elem=graph[element.elem][i];
                q.push(aux);
                visited[graph[element.elem][i]]=aux.d;
            }
            else
                if(1+element.d<visited[graph[element.elem][i]])
            {
                aux.d=1+element.d;
                aux.elem=graph[element.elem][i];
                q.push(aux);
                visited[graph[element.elem][i]]=aux.d;
            }
        }
        q.pop();
    }
}
int main()
{
    ifstream f("bfs.in");
    f>>n>>m>>s;
    graph.resize(n);
    visited.resize(n,-1);
    int x, y;
    for(int i=0;i<m;i++)
    {
        f>>x>>y;
        x--;
        y--;
        graph[x].push_back(y);
    }
    s--;
    bfs(s);
    ofstream g("bfs.out");
    for(int i=0;i<n;i++)
    {
        g<<visited[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}