import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
 
class Nod {
    public int id;
    int cost = -1; // cost pana aici pentru bfs cand o muchie costa 1
    int timp; // timp de atingere
    public boolean viz;
    public ArrayList<Nod> vecini = new ArrayList<Nod>();
 
    // public ArrayList<Integer> costuri = new ArrayList<Integer>();
 
    public Nod(int id) {
        super();
        this.id = id + 1;
    }
 
    @Override
    public String toString() {
        return "" + this.id;
    }
 
}
 
public class Main {
 
    public static int sursa;
    public static int timp;
 
    public static void main(String[] args) throws FileNotFoundException {
 
        ArrayList<Nod> g = new ArrayList<Nod>();
        readData(g);
        sursa--; // pentru ca lcram cu indexi si 2 e de fapt 1
        BFS(g);
        // afiG(g);
        printData(g);
 
    }
 
    public static void BFS(ArrayList<Nod> g) throws FileNotFoundException {
 
        LinkedList<Nod> coada = new LinkedList<Nod>();
 
        Nod curent;
        // pentru ficare nod din g incercam sa parcurgem BFS
 
        // daca nodul nu a fost vizitat deja il punem in coada
 
        coada.add(g.get(sursa));
        g.get(sursa).cost = 0;
        g.get(sursa).viz = true;
        g.get(sursa).timp = timp++;
 
        // cat timp avem noduri in coada extragem cate un nod si ii punem vecinii
        // nevzititati in coada
        while (!coada.isEmpty()) {
            // extragem de la inceput
 
            curent = coada.remove();
            for (Nod nod : curent.vecini) {
                if (nod.viz == false) {
 
                    coada.add(nod);
                    nod.viz = true;
                    nod.cost = curent.cost + 1;
                    nod.timp = timp++;
                }
            }
        }
 
    }
 
    public static void readData(ArrayList<Nod> g) throws FileNotFoundException {
        int noduri;
        int muchii;
 
        Scanner s = new Scanner(new FileInputStream("bfs.in"));
 
        noduri = s.nextInt();
        muchii = s.nextInt();
        sursa = s.nextInt();
 
        for (int i = 0; i < noduri; i++) {
 
            g.add(new Nod(i));
        }
 
        for (int i = 0; i < muchii; i++) {
            int nod1 = s.nextInt() - 1;
            int nod2 = s.nextInt() - 1;
            g.get(nod1).vecini.add(g.get(nod2));
 
            // pentru neorientat
            // g.get(nod1).vecini.add(g.get(nod2));
        }
 
        s.close();
 
    }
 
    public static void printData(ArrayList<Nod> g) throws FileNotFoundException {
        PrintWriter writer = new PrintWriter(new FileOutputStream("bfs.out"));
 
        for (Nod nod : g) {
            writer.write(String.valueOf(nod.cost) + " ");
        }
 
        writer.close();
    }
 /*
    public static void afiG(ArrayList<Nod> g) {
        for (Nod nod : g) {
            System.out.print("id " + nod.id + " timp " + nod.timp + "cost " + nod.cost + " : ");
            for (Nod n : nod.vecini) {
                System.out.print(n.id + " ");
            }
            System.out.println();
        }
    }*/
}