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

using namespace std;

int n,m;

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

vector<vector<int> > graf;
vector<bool> visited;
vector<int> distanta;

void bfs(int x)
{
    int i,element,j=1;;
    if(x<0 ||x>n-1)
        return;
    queue<int> q;
    bool found;
    q.push(x);
    visited[x]=true;
    while(!q.empty())
    {
        found=false;
        element=q.front();
        for(i=0; i<graf[element].size(); i++)
        {
            if(!visited[graf[element][i]])
            {
                q.push(graf[element][i]);
                visited[graf[element][i]]=true;
                distanta[graf[element][i]]=j;
                found=true;
            }
        }
        q.pop();
        if(found)
        j++;
    }
}

int main()
{
    int i,s,x,y;
    f>>n>>m>>s;
    graf.resize(n);
    visited.resize(n,false);
    distanta.resize(n,-1);
    for(i=0; i<m; i++)
    {
        f>>x>>y;
        if(x!=y)
        {
            x--;
            y--;
            graf[x].push_back(y);
        }
    }
    bfs(s-1);
    distanta[s-1]=0;
    for(i=0;i<distanta.size();i++)
        g<<distanta[i]<<" ";
}