#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

queue <int> q;
unsigned short int mat[100000][100000/15+1];
short int cost[100000];
int n, m, s;


int get(int i, int j, int k)
{
    unsigned short int r = 1;
    r = r << (15-k);
    if((mat[i][j] & r)!=0)
        return j*15+k;
    else return 0;

}

void read(int x, int y)
{
    unsigned short int r=1<<15;
    r = r >> y%15;
    mat[x][y/15] = mat[x][y/15] | r;
}

void bfs(int start)
{
    int a,vecin;
    q.push(start);
    while(!q.empty())
    {
        a=q.front();
        for(int i=0; i<n/15+1; i++)
        {
            for(int j=0; j<15; j++)
            {
                vecin = get(a, i, j);
                if(vecin !=0 )
                    if(cost[vecin]==-1)
                    {
                        cost[vecin] = cost[a]+1;
                        q.push(vecin);
                    }
            }
        }
        q.pop();
    }
}


int main()
{
    ifstream in("bfs.in");
    int x, y;
    in>>n>>m>>s;
    for(int i=0; i<m; i++)
    {
        in>>x>>y;
        read(x,y);
    }
    for(int i=1; i<=n; i++)
        cost[i]=-1;
    cost[s]=0;
    in.close();
    bfs(s);
    ofstream out("bfs.out");
    for(int i=1; i<=n; i++)
        out<<cost[i]<<" ";
    out.close();
    return 0;

}