题目描述

有 $n$ 个城市和 $m$ 条双向道路，每条道路经过一次记 1 步。求从城市 $s$ 到所有城市的最少道路数；不可达输出 -1。

输入格式

第一行 $n,m,s$，随后 $m$ 行每行一条道路 $u,v$。

输出格式

一行输出 $n$ 个整数。

样例

5 4 1
1 2
2 3
1 4
4 3

0 1 2 1 -1

数据规模与约定

$1\le n\le200000$，$0\le m\le300000$。