#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define maxn 100010
using namespace std;


ifstream f("bfs.in");
ofstream g("bfs.out");

int M,N,S;


bool vis[maxn];
vector <int> A[maxn];
int dist[maxn];

void BFS(int start)
{

    queue <int> c;
    c.push(start);
        int p;
        dist[start] = 0;
        vis[start] = true;

    while(!c.empty())
    {
        p = c.front();
        c.pop();


        for(unsigned int i = 0;i<A[p].size();i++){
                if(!vis[A[p][i]]){
                    vis[A[p][i]] = true;
                c.push(A[p][i]);
                dist[A[p][i]] = dist[p] + 1;
                }

        }

    }


}

int main()
{

    int i,x,y;

    f>>N>>M>>S;
    for(i = 1; i<=M; i++)
    {
        f>>x>>y;
        A[x].push_back(y);
    }


    for(i = 1; i<=N;i++)
        dist[i] = -1;

    BFS(2);
    for(int i = 1; i<= N; i++)
        g<<dist[i]<<" ";





    return 0;
}