Cho một đồ thị vô hướng gồm N đỉnh đánh số từ 1 tới N và M cạnh. Độ 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.

Yêu cầu: 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<=100000, M<=100000, 1<=S<=N)
• M dòng sau mỗi dòng gồm 2 số thể hiện 2 đầ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.