Cho đồ thị vô hướng \(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\) tới \(m\).

Độ dài của mỗi cạnh có giá trị là \(1\). Một đồ thị sẽ có \(1\) nút trung tâm \(s\).

Với mỗi đỉnh có thể tới được từ đỉnh \(s\), tính khoảng cách ngắn nhất từ đỉnh đó tới \(S\) và in ra các đỉnh theo thứ tự khoảng cách ngắn nhất tăng dần.

Lưu ý : Nếu \(2\) đỉnh có khoảng cách bằng nhau thì nhãn nào nhỏ hơn sẽ đứng trước.

Input

• Dòng đầu gồm 3 số nguyên \(n, m, s\) \((n, m \leq 10^5, 1 \leq s \leq n)\)
• \(m\) dòng sau mỗi dòng gồm hai số \(u\), \(v\) thể hiện hai đầu của một cạnh.

Output

• In ra số dòng tương ứng với số đỉnh có thể tới được từ \(s\) theo thứ tự khoảng cách ngắn nhất tăng dần.
• Trên mỗi dòng in ra nhãn của đỉnh đó và khoảng cách ngắn nhất của đỉnh đó tới \(s\).

Sample Input

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

Sample Output

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