时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给出 \(n\) 个顶点（编号为 \(1\sim n\)），\(m\) 条边的无向连通无权简单图，请输出从源点 \(s\) 出发到每个点的最短路径长度。

【输入格式】

　　第一行包含三个整数：\(n,m,s\)，表示图的顶点、边的数目和源点。
　　接下来的 \(m\) 行，每行包含 2 个整数：\(a,b\)（\(1 ≤ a, b ≤ n\)），表示图的一条边关联的顶点为\(a,b\)。

【输出格式】

　　包含 \(n\) 行，分别表示源点 \(s\) 到 \(1,2,…,n\) 的最短路径长度。

【输入输出样例】

　Input

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

　Output

0
1
1
2
3

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤n≤50000\)，\(1≤m≤100000\)。

【来源】

　　Mr.he