#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>
#include <queue>

using namespace std;

/// infoarena BFS

ifstream fin("bfs.in");ofstream fout("bfs.out");

int n,m,s,v[100001],id[100002];

struct muchie
{
    int x,y;
}U[1000001];

bool ordine(muchie id1,muchie id2)
{
    if (id1.x!=id2.x)
        return id1.x<id2.x;
    return id1.y<id2.y;
}

int find_id(int val,int lo,int hi)
{
    if(lo>hi)
        return -1;
    else
    {
        int mid=(lo+hi)/2;
        if (U[mid].x==val)
        {
            while (U[mid].x==val)
                mid--;
            return mid+1;
        }
        else
        {
            if (U[mid].x>val)
                return find_id(val,lo,mid-1);
            else
                return find_id(val,mid+1,hi);
        }
    }
}

void BFS()
{
    v[s]=1;
    queue <int> Q;
    Q.push(s);
    while(!Q.empty())
    {
        int nod=Q.front();
        for (int i=id[nod];U[i].x==nod;i++)
            if (v[U[i].y]==0)
            {
                Q.push(U[i].y);
                v[U[i].y]=v[nod]+1;
            }
        Q.pop();
    }
}

int main()
{
    fin>>n>>m>>s;
    for (int i=1;i<=m;i++)
        fin>>U[i].x>>U[i].y;
    sort(U+1,U+m+1,ordine);
    id[0]=0;id[n+1]=m+1;
    for (int i=1;i<=n;i++)
        id[i]=find_id(i,id[i-1]+1,m+1);
    BFS();
    for (int i=1;i<=n;i++)
        cout<<v[i]-1<<" ";
    return 0;
}