use std::collections::VecDeque;
use std::fs::File;
use std::io::prelude::*;


struct Graf{
    g: Vec<Vec<i32>>
}
impl Graf{
    fn new(len: usize) -> Self{
        let mut v: Vec<Vec<i32>> = Vec::new();
        v.resize(len,vec![]);
        Graf{g: v}
    }
    fn bfs(&self, x: i32, len : usize){
        let mut f: Vec<bool> = Vec::new();
        f.resize(len, false);
        let mut d: Vec<i32> = Vec::new();
        d.resize(len, 0);

        let mut q: VecDeque<i32> = VecDeque::new();
        q.push_back(x);
        d[x as usize] = 0;
        f[x as usize] = true;
        while !q.is_empty() {
            let t = *q.front().unwrap();
            q.pop_front();
            
            for i in self.g[t as usize].iter() {
                if !f[*i as usize]{
                    f[*i as usize] = true;
                    d[*i as usize] = d[t as usize] + 1;
                    q.push_back(*i);
                }
            }
        }

        let mut outfile = File::create("bfs.out").unwrap();
        let els = -1;

        for i in 1..len{
            if f[i] {
                outfile.write(d[i].to_string().as_bytes()).unwrap();
                outfile.write( " ".as_bytes()).unwrap();
            }
            else {
                outfile.write(els.to_string().as_bytes()).unwrap();
                outfile.write( " ".as_bytes()).unwrap();
            }
        }
        
    }
}



pub fn main() {
    let mut input = File::open("bfs.in").unwrap();
    let mut buffer = String::new();
    input.read_to_string(&mut buffer).unwrap();
    let vec : Vec<&str> = buffer.lines().collect();
    let (n, m, k) : (i32, i32, i32);

    let mut vec2 : Vec<&str> =  vec[0].trim().split(" ").collect();
    n = vec2[0].parse().unwrap();
    m = vec2[1].parse().unwrap();
    k = vec2[2].parse().unwrap();

    let mut g:Graf = Graf::new((n + 1) as usize);


    for i in 1..((m + 1) as usize){
        vec2.clear();
        vec2 = vec[i].trim().split(" ").collect();
        let a: i32 = vec2[0].parse().unwrap();
        let b: i32 = vec2[1].parse().unwrap();
        g.g[a as usize].push(b);
    }

    g.bfs(k, (n + 1) as usize);

}