package com.company;

import java.io.File;
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
import java.io.FileWriter;
public class Main {

    static int [] distanta (ArrayList<ArrayList<Integer>> graf, int S, int N)
    {
        int [] dist= new int[100005];
        Queue <Integer> q = new LinkedList<>();
        q.add(S);

        for(int i=1; i<= N; i++)
        {
            dist[i]=10000000;

        }
        dist[S]=0;
        while (q.size()!=0)
        {
            int current= q.peek();
            q.remove();
            ArrayList<Integer> vecini= graf.get(current);

            for(int i=0; i< vecini.size(); i++)
            {
                int newdist= dist[current] + 1;
                if (newdist < dist[vecini.get(i)])
                {
                    dist[vecini.get(i)]= newdist;
                    q.add(vecini.get(i));
                }
            }
        }
        return dist;
    }

    public static void main (String [] args)
    {
        ArrayList<ArrayList<Integer>> graf= new ArrayList<ArrayList<Integer>> ();
        int N;
        int M;
        int S;


        File myFile= new File("bfs.in");
        Scanner myReader=null;
        try {
            myReader= new Scanner (myFile);
        }   catch (IOException e) {}

        N= myReader.nextInt();
        M= myReader.nextInt();
        S= myReader.nextInt();


        for (int i=0; i<=N; i++)
        {
            graf.add(new ArrayList<>());
        }
        for (int i=1; i<=M; i++)
        {
            int x = myReader.nextInt();
            int y = myReader.nextInt();
            ArrayList<Integer> vecini = graf.get(x);
            vecini.add(y);
        }
        try
        {
            FileWriter out = new FileWriter("bfs.out");
            int [] v= distanta(graf,S,N);
            for (int i =1; i<=N; i++)
            {
                if(v[i]==10000000)
                {
                    v[i]=-1;
                }
                Integer w= v[i];
                out.write(w.toString()+" ");
            }
            out.close();
        } catch (IOException e) {}





        //System.out.println("h");
    }


}