Cho đơn đồ thị \(G=(V,E)\) gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ \(1\) tới \(n\) và các cạnh được đánh số từ \(1\) đến \(m\). Và đỉnh trung tâm \(S\). Với mỗi đỉnh có thể đi từ \(S\), hãy tìm độ dài đường đi ngắn nhất từ \(S\) đến đỉnh đó. Biết rằng độ dài của một đường đi là số đỉnh nằm trên đường đi đó.

Input

• Dòng \(1\): Chứa ba số nguyên dương \(n,m\) và \(s(1 \leq n,m \leq 10^5, 1 \leq s \leq n)\)
• \(m\) dòng tiếp theo: Dòng thứ \(i\) có dạng \(2\) số nguyên \(u\),\(v\). Trong đó \(u\),\(v\) là chỉ số hai đỉnh đầu mút của cạnh thứ \(i\).

Output

• Ghi một dòng duy nhất ghi \(n\) số nguyên là độ dài đường đi ngắn nhất từ \(s\) đến mọi đỉnh, nếu từ \(s\) không thể đi đến thì in \(-1\).

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

 0 1 1 2 3 4 -1