#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
queue <int> q;
vector<int> v[100001];
int n,m,ver[100001],x;
int main()
{
    int i,j;
    in>>n>>m>>x;
    for(int l=1;l<=m;l++)
    {
        in>>i>>j;
        v[i].push_back(j);
    }
    for(i=1;i<=n;i++)
        sort(v[i].begin(),v[i].end());
    ver[x]=1;
    q.push(x);
    while(!q.empty())
    {
        int k=q.front();
        j=v[k].size();
        for(i=0;i<j;i++)
        {
            if(ver[v[k][i]]==0)
            {
                ver[v[k][i]]=ver[k]+1;
                q.push(v[k][i]);
            }
        }
        q.pop();
    }
    for(i=1;i<=n;i++)
    {
        if(i==x)
            out<<0<<' ';
        else
        if(ver[i]==0)
            out<<-1<<' ';
        else
            out<<ver[i]-1<<' ';
    }
    return 0;
}