use std::fs;
use std::io::{BufRead, BufReader, Write};
 
const TASK_NAME: &str = "bfs";
 
fn solve_task<R: BufRead, W: Write>(mut input: R, mut output: W) {
    let mut buf = String::new();
    input.read_line(&mut buf).unwrap();
    let (n, m, s) = {
        let mut iter = buf.split_whitespace().map(|x| x.parse::<usize>().unwrap());
 
        let n = iter.next().unwrap();
        let m = iter.next().unwrap();
        let s = iter.next().unwrap() - 1;
        (n, m, s)
    };

    let mut graph = vec![vec![]; n];
    for _ in 1..=m {
        buf.clear();
        input.read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace().map(|x| x.parse::<usize>().unwrap());
        let a = iter.next().unwrap() - 1;
        let b = iter.next().unwrap() - 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;
    }
 
    writeln!(
        output,
        "{}",
        dist.iter()
            .map(|x| format!("{}", x))
            .collect::<Vec<String>>()
            .join(" ")
    )
    .unwrap();
}
 
fn main() {
    let input = BufReader::new(
        fs::File::open(format!("{}.in", TASK_NAME).as_str()).expect("Input file not found"),
    );
    let output =
        fs::File::create(format!("{}.out", TASK_NAME).as_str()).expect("Output file not created");
    solve_task(input, output);
}