use std::collections::VecDeque;
use std::error::Error;
use std::fs::File;
use std::io::{BufRead, BufReader, Write};

const N: usize = 100_005;

fn main() -> Result<(), Box<dyn Error>> {
    let mut fin = BufReader::new(File::open("bfs.in").unwrap());
    let mut fout = File::create("bfs.out").unwrap();

    let mut buf = String::new();

    fin.read_line(&mut buf)?;
    let [n, m, s] = buf
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap())
        .collect::<Vec<usize>>()[..]
    else {
        panic!("invalid input format on line 1");
    };

    let mut graf = vec![vec![]; N];

    for i in 0..m {
        buf.clear();
        fin.read_line(&mut buf)?;
        let [x, y] = buf
            .trim()
            .split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<usize>>()[..]
        else {
            panic!("invalid input format on line {}", i + 1);
        };

        graf[x].push(y);
    }

    let mut q = VecDeque::<usize>::new();
    let mut visited = vec![false; N];
    visited[s] = true;
    let mut dist = vec![-1; N];
    dist[s] = 0;
    q.push_back(s);
    while !q.is_empty() {
        let now = q.pop_front().unwrap();
        for &nod in &graf[now] {
            if !visited[nod] {
                visited[nod] = true;
                dist[nod] = dist[now] + 1;
                q.push_back(nod);
            }
        }
    }

    for i in dist[1..=n].into_iter() {
        fout.write_fmt(format_args!("{} ", i))?;
    }

    Ok(())
}