// https://infoarena.ro/problema/dfs

use std::{
    collections::*, fmt::*, fs::{write, *}, str::*
};

fn split_in_x_var<T: FromStr>(string: &str) -> Vec<T> where T::Err: Debug {
    string.split_whitespace().map(|x| x.parse::<T>().unwrap()).collect::<Vec<T>>()
}

fn split_in_x<const N: usize, T: FromStr + Debug>(string: &str) -> [T; N] where T::Err: Debug {
    string.split_whitespace().map(|x| x.parse::<T>().unwrap()).collect::<Vec<T>>().try_into().unwrap()
}

fn bfs(nod_start: usize, nod_de_gasit: usize, nodurile: &Vec<HashSet<usize>>) -> Option<usize> {
    if nod_start == nod_de_gasit {
        return Some(0);
    }

    let mut gasite_tot = HashSet::from([nod_start]);
    let mut gasite = HashSet::from([nod_start]);

    for lungime in 1.. {
        let mut gasite_noi = HashSet::<usize>::new();

        for gasit in &gasite {
            if nodurile[*gasit].contains(&nod_de_gasit) {
                return Some(lungime);
            }
            gasite_noi.extend(&nodurile[*gasit]);
        }

        if gasite_noi.difference(&gasite_tot).last().is_none() {
            return None;
        }

        gasite_tot.extend(&gasite_noi);
        gasite = gasite_noi;
    }
    return None
}

fn main() {
    let content = read_to_string("bfs.in").unwrap();
    let mut lines = content.lines();
    let [noduri, _muchii, mut nod]: [usize; 3] = split_in_x(lines.next().unwrap());
    nod -= 1;

    let mut adiacente = vec![HashSet::new(); noduri];

    for line in lines {
        let [muchie1, muchie2]: [usize; 2] = split_in_x(line);
        adiacente[muchie1 - 1].insert(muchie2 - 1);
    }

    let mut distante_pana_la_nod = vec![-1; noduri];
    distante_pana_la_nod[nod] = 0;

    let mut gasite = HashSet::from([nod]);
    for lungime in 1i32.. {
        let mut gasite_noi = HashSet::<usize>::new();

        for gasit in &gasite {
            for adiacent in &adiacente[*gasit] {
                if distante_pana_la_nod[*adiacent] == -1 {
                    distante_pana_la_nod[*adiacent] = lungime;
                    gasite_noi.insert(*adiacent);
                }
            }
        }

        if gasite_noi.is_empty() {
            break;
        }

        gasite = gasite_noi;
    }

    let res = distante_pana_la_nod.iter().map(i32::to_string).collect::<Vec<_>>().join(" ");

    write("bfs.out", res).unwrap();
}