#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin ("bfs.in");
ofstream fout ("bfs.out");
queue<int> q;
vector<vector<int>> ma;
vector<int> v;

int main()
{
    int n,m,s;
    fin>>n>>m>>s;
    for(int k=0;k<=n;k++)
    {
        ma.push_back(vector<int>());
        v.push_back(-1);
    }
    int c,cc;
    for(int k=1;k<=m;k++)
    {
        fin>>c>>cc;
        ma[c].push_back(cc);
    }
    q.push(s);
    v[s]=0;
    vector<int> ::iterator k;
    int ft;
    while(!q.empty())
    {
        ft=q.front();
        for(k=ma[ft].begin();k!=ma[ft].end();k++)
        {
            if(v[*k]==-1)
            {
                q.push(*k);
                v[*k]=v[ft]+1;
            }
        }
        q.pop();
    }
    for(k=v.begin()+1;k!=v.end();k++)
    {
        fout<<*k<<" ";
    }
    return 0;
}