#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define INF 999999999
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n,m,s;
vector< vector<int> > mat;
vector<bool> viz;
vector<int> roads;
queue<int> q;
int main()
{
    fin>>n>>m>>s;
    vector<int> v;
    mat.assign(n,v);
    viz.assign(n,false);
    roads.assign(n,INF);
    for(int i=0;i<m;i++)
    {
        int k1,k2;
        fin>>k1>>k2;
        mat[k1-1].push_back(k2-1);
    }
    roads[s-1] = 0;
    q.push(s-1);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        viz[x] = true;
        for(int i=0;i<mat[x].size();i++)
        {
            if(roads[x] + 1 < roads[mat[x][i]])
            {
                roads[mat[x][i]] = roads[x] + 1;
            }
            if(viz[mat[x][i]] == false) q.push(mat[x][i]);
        }
    }
    for(int i=0;i<n;i++)
    {
        if(roads[i] != INF) fout<<roads[i]<<" ";
        else fout<<"-1"<<" ";
    }
}