Bài toán

Cho một đồ thị vô hướng \(G\) gồm \(N\) đỉnh đánh số từ \(1\) đến \(N\), được nối với nhau bằng \(M\) cạnh. Mỗi cạnh có độ dài bằng \(1\). Đồ thị này sẽ có một đỉnh trung tâm là \(C\).

Cho biết đỉnh \(C\), hãy tính khoảng cách đường đi ngắn nhất từ đỉnh \(C\) đến các đỉnh trong đồ thị.

Input

• Dòng đầu tiên gồm \(3\) số nguyên dương \(N, M, C\) (\(1 \leq N, M \leq 10^5, 1 \leq C \leq N\)).
• \(M\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(u, v\) thể hiện một cạnh nối giữa đỉnh \(u\) và đỉnh \(v\).

Output

• In ra \(N\) dòng, dòng thứ \(i\) là khoảng cách từ đỉnh \(C\) đến đỉnh thứ \(i\).
• Biết khoảng cách từ \(C\) đến \(C\) bằng \(0\) và nếu không có đường đi, khoảng cách bằng -1.

Sample Test

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

0
1
1
2
3
4