无权图最短距离

题目描述

给定一张无向、无权图和起点 s。请计算起点 s 到每个顶点经过的最少边数。

若某个顶点无法从 s 到达，则其距离为 -1。

输入格式

第一行三个整数 n、m、s。

接下来 m 行，每行两个整数 u、v，表示一条无向边。

输出格式

输出 n 个整数，第 i 个整数表示从 s 到顶点 i 的最短距离。

7 7 1
1 2
1 3
2 4
3 5
4 6
5 6
6 7

0 1 1 2 2 3 4

数据范围

• 1 <= n <= 100000
• 0 <= m <= 200000
• 1 <= s <= n