// https://infoarena.ro/problema/bfs

mod helperlib {
    use std::{fs::*, io::*, path::*};

    pub trait ReadFromReader {
        fn read<R: BufRead>(reader: &mut R) -> Result<Self> where Self: Sized;
    }

    macro_rules! impl_num_read {
        ($($typ: ty)*) => {$(
            impl ReadFromReader for $typ {
                fn read<R: BufRead>(reader: &mut R) -> Result<Self> {
                    let mut res = None;

                    let minus = Some(b'-') == reader.fill_buf()?.first().copied();
                    if minus {
                        if Self::MIN == 0 {
                            let err = format!("Could not parse negative number as {}.", std::any::type_name::<Self>());
                            return Err(std::io::Error::new(ErrorKind::InvalidData, err));
                        }
                        reader.consume(1);
                    }

                    loop {
                        let Some(&b) = reader.fill_buf()?.first() else { break };
                        if b.is_ascii_digit() {
                            reader.consume(1);

                            let b = b as Self;
                            if let Some(res) = res.as_mut() {
                                *res *= 10;
                                if minus {
                                    *res -= b - b'0' as Self;
                                } else {
                                    *res += b - b'0' as Self;
                                }
                            } else {
                                if minus {
                                    res = Some(b'0' as Self - b);
                                } else {
                                    res = Some(b - b'0' as Self);
                                }
                            }
                        } else {
                            break;
                        }
                    }

                    if let Some(res) = res {
                        Ok(res)
                    } else {
                        let err = format!("Could not parse type {}.", std::any::type_name::<Self>());
                        Err(std::io::Error::new(ErrorKind::InvalidData, err))
                    }
                }
            }
        )*};
    }

    impl_num_read!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);

    impl ReadFromReader for char {
        fn read<R: BufRead>(reader: &mut R) -> Result<Self> {
            let invalid = || std::io::Error::new(ErrorKind::InvalidData, "Invalid UTF-8 sequence.");

            let mut buf = [0u8; 4];
            reader.read_exact(&mut buf[..1]).map_err(|e| {
                if e.kind() == ErrorKind::UnexpectedEof {
                    std::io::Error::new(ErrorKind::UnexpectedEof, "Could not read char: end of input.")
                } else {
                    e
                }
            })?;

            let len = match buf[0] {
                0x00..=0x7F => 1,
                0xC0..=0xDF => 2,
                0xE0..=0xEF => 3,
                0xF0..=0xF7 => 4,
                _ => return Err(invalid()),
            };
            reader.read_exact(&mut buf[1..len])?;

            std::str::from_utf8(&buf[..len])
                .map_err(|_| invalid())?
                .chars()
                .next()
                .ok_or_else(invalid)
        }
    }


    pub struct Reader<R> {
        reader: BufReader<R>
    }

    impl Reader<File> {
        #[allow(dead_code)]
        pub fn new(path: impl AsRef<Path>) -> Result<Self> {
            Ok(Self::from_reader(File::open(path)?))
        }
    }

    impl Reader<Stdin> {
        #[allow(dead_code)]
        pub fn new_stdin() -> Self {
            Self::from_reader(stdin())
        }
    }

    impl<R: Read> Reader<R> {
        pub fn from_reader(reader: R) -> Self {
            Reader { reader: BufReader::new(reader) }
        }

        // pub fn read<T: ReadFromReader>(&mut self) -> Result<T> {
        //     T::read(&mut self.reader)
        // }

        #[allow(dead_code)]
        pub fn read_whitespaced<T: ReadFromReader>(&mut self) -> Result<T> {
            while self.reader.fill_buf()?.first().is_some_and(u8::is_ascii_whitespace) { self.reader.consume(1); }
            T::read(&mut self.reader)
        }

        #[allow(dead_code)]
        pub fn read_line_of<T: ReadFromReader>(&mut self) -> impl Iterator<Item = T> {
            std::iter::from_fn(|| {
                loop {
                    let &b = self.reader.fill_buf().ok()?.first()?;
                    if b.is_ascii_whitespace() {
                        self.reader.consume(1);
                        if b == b'\n' { return None; }
                    } else {
                        return T::read(&mut self.reader).ok()
                    }
                }
            })
        }
    }



    pub trait WriteToWriter {
        fn write<W: Write>(&self, writer: &mut W) -> Result<()>;
    }

    macro_rules! impl_num_write {
        ($($typ: ty)*) => {$(
            impl WriteToWriter for $typ {
                fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
                    if *self == 0 {
                        writer.write_all(b"0")
                    } else {
                        const BUF_LEN: usize = 128;
                        let mut buf = [0; BUF_LEN];
                        let mut buf_index = BUF_LEN - 1;
                        let mut copy = *self;

                        while copy != 0 {
                            buf[buf_index] = b'0' + ((copy % 10) as i8).unsigned_abs();
                            copy /= 10;
                            buf_index -= 1;
                        }

                        #[allow(unused_comparisons)]
                        if *self < 0 {
                            buf[buf_index] = b'-';
                        } else {
                            buf_index += 1;
                        }

                        writer.write_all(&buf[buf_index..])
                    }
                }
            }
        )*};
    }

    impl_num_write!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);

    impl WriteToWriter for char {
        fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
            let mut buf = [0; size_of::<Self>()];
            self.encode_utf8(&mut buf);
            writer.write_all(&buf[..self.len_utf8()])
        }
    }

    impl WriteToWriter for str {
        fn write<W: Write>(&self, writer: &mut W) -> Result<()> {
            writer.write_all(self.as_bytes())
        }
    }

    pub struct Writer<W: Write> {
        writer: BufWriter<W>
    }

    impl Writer<File> {
        #[allow(dead_code)]
        pub fn new(path: impl AsRef<Path>) -> Result<Self> {
            Ok(Self::from_writer(File::create(path)?))
        }
    }

    impl Writer<Stdout> {
        #[allow(dead_code)]
        pub fn new_stdout() -> Self {
            Self::from_writer(stdout())
        }
    }

    impl<W: Write> Writer<W> {
        #[allow(dead_code)]
        pub fn from_writer(writer: W) -> Self {
            Writer { writer: BufWriter::new(writer) }
        }

        #[allow(dead_code)]
        pub fn flush(&mut self) -> Result<()> {
            self.writer.flush()
        }

        // pub fn write<T: WriteToWriter + ?Sized>(&mut self, val: &T) -> Result<()> {
        //     val.write(&mut self.writer)
        // }

        #[allow(dead_code)]
        pub fn write_spaced<T: WriteToWriter + ?Sized>(&mut self, val: &T) -> Result<()> {
            val.write(&mut self.writer)?;
            ' '.write(&mut self.writer)
        }

        #[allow(dead_code)]
        pub fn write_line<T: WriteToWriter + ?Sized>(&mut self, val: &T) -> Result<()> {
            val.write(&mut self.writer)?;
            '\n'.write(&mut self.writer)
        }
    }
}
use helperlib::*;

fn main() {
    let mut input = Reader::new("bfs.in").unwrap();

    let noduri = input.read_whitespaced().unwrap();
    let muchii = input.read_whitespaced().unwrap();
    let nod_sursa = input.read_whitespaced::<usize>().unwrap() - 1;

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

    for _ in 0..muchii {
        let muchie1: usize = input.read_whitespaced().unwrap();
        let muchie2: usize = input.read_whitespaced().unwrap();
        adiacente[muchie1 - 1].push(muchie2 - 1);
    }

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

    let mut gasite = Vec::from([nod_sursa]);
    for lungime in 1i32.. {
        let mut gasite_noi = Vec::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.push(adiacent);
                }
            }
        }

        if gasite_noi.is_empty() {
            break;
        }

        gasite = gasite_noi;
    }

    let mut output = Writer::new("bfs.out").unwrap();
    for distanta in distante_pana_la_nod {
        output.write_spaced(&distanta).unwrap();
    }
}