#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n,s,lung[100010];

vector<int> lv[100010];
queue<int> q;

bool viz[100010];

int main()
{
    FILE *f=fopen("bfs.in","r");
    int m,i,x,y;
    fscanf(f,"%d%d%d",&n,&m,&s);
    for(i=1;i<=n;i++)lung[i]=-1;
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        lv[x].push_back(y);
    }
    lung[s]=0;
    viz[s]=1;
    q.push(s);
    vector<int>::iterator ii;
    int lg;
    while(!q.empty())
    {
        lg=lung[x=q.front()];
        q.pop();
        for(ii=lv[x].begin();ii!=lv[x].end();++ii)
            if(!viz[*ii])
            {
                viz[*ii]=1;
                lung[*ii]=lg+1;
                q.push(*ii);
            }
    }
    fclose(f);
    f=fopen("bfs.out","w");
    for(i=1;i<=n;i++)
        fprintf(f,"%d ",lung[i]);
    return 0;
}