#include <fstream>
#include <queue>
#include <vector>
#define oo 1<<30
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
const int nmax=100005;
int n,m,s,a,b,D[nmax];
vector < pair<int,int> > v[nmax];
struct compara
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};
priority_queue <int, vector <int> , compara> coada;
vector <bool> vizitat;
void citire()
{
    fin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        v[a].push_back(make_pair(b,1));
    }
}

void dijsktra2(int nod_start)
{
    for(int i=1;i<=n;i++)
            D[i]=oo;

            D[nod_start]=0;
            coada.push(nod_start);
            vizitat[nod_start]=true;

        while(!coada.empty())
        {
            int nod_curent=coada.top();
            coada.pop();
            vizitat[nod_curent]=false;

            for(int j=1;j<=v[nod_curent].size();j++)
            {
                int vecin=v[nod_curent][j].first;
                int cost=v[nod_curent][j].second;

                if(cost+D[nod_curent]<D[vecin])
                {
                    D[vecin]=cost+D[nod_curent];
                    if(vizitat[vecin]==false)
                    {
                        coada.push(vecin);
                        vizitat[vecin]=true;
                    }
                }
            }
        }

}

void afiseaza()
{
    for(int i=1;i<=n;i++)
    {
        if(D[i]==oo) fout<<-1<<" ";
        else fout<<D[i]<<" ";
    }
}
int main()
{
citire();
dijsktra2(s);
afiseaza();



    return 0;
}