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

---

【问题描述】

　　重庆城里有N个车站，M条双向公路连接其中的某些站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其它车站。有公路的两个车站之间有一辆公共汽车运行于这两个车站之间。

　　Mr.H 家住第 \(S\) 个车站，打算用漫长暑假走完重庆城的每个角落，现在需要知道从他家出发到每个车站的最少换乘车次数。(从 \(S\) 出发上车算 1 次换乘)

【输入格式】

　　第一行为车站数目和公路的数目：\(N\) 和 \(M\)。
　　接下来 \(M\) 行，每行三个整数 \(x,y(1≤x,y≤N)\)，为公路连接的两个车站编号。
　　最后一行一个整数 \(S\)。

【输出格式】

　　共 \(N\) 行，分别表示从 \(S\) 到车站 \(1、2、…、N\) 的最少换乘次数。

【输入输出样例】

　Input

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

　Output

1
1
1
2
2
3

【数据说明】

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

【来源】

　　Mr.he