use std::collections::VecDeque;
use std::fs;

const TASK_NAME: &str = "bfs";

struct InputReader(VecDeque<String>);

impl InputReader {
    fn new(s: String) -> InputReader {
        InputReader(VecDeque::from(
            s.split_whitespace()
                .map(|s| s.to_string())
                .collect::<Vec<String>>(),
        ))
    }
    fn next<A: std::str::FromStr>(&mut self) -> A {
        match self.0.pop_front().unwrap().parse::<A>() {
            Ok(result) => result,
            _ => panic!("Parse failed."),
        }
    }
    fn len(&self) -> usize {
        self.0.len()
    }
}

fn solve_task(mut input: InputReader) -> String {
    let n = input.next::<usize>();
    let m = input.next::<usize>();
    let s = input.next::<usize>() - 1;
    let mut graph = vec![vec![]; n];
    for _ in 0..m {
        let a = input.next::<usize>() - 1;
        let b = input.next::<usize>() - 1;
        graph[a].push(b);
    }
    let mut dist = vec![-1; n];
    let mut queue = Vec::with_capacity(n);

    dist[s] = 0;
    queue.push(s);

    let mut at = 0;
    while at < queue.len() {
        let node = queue[at];
        for neigh in &graph[node] {
            if dist[*neigh] == -1 {
                dist[*neigh] = dist[node] + 1;
                queue.push(*neigh);
            }
        }
        at += 1;
    }

    dist.iter()
        .map(|x| format!("{}", x))
        .collect::<Vec<String>>()
        .join(" ")
}

fn main() {
    let input_file = fs::read_to_string(format!("{}.in", TASK_NAME).as_str()).expect("input file");
    let output = solve_task(InputReader::new(input_file));
    fs::write(format!("{}.out", TASK_NAME), output).expect("output file");
}