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~, hãy 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.

Yêu cầu: Viết chương trình thực hiện yêu cầu trên.

Input

• Dòng đầu gồm ~3~ số nguyên ~n, m~ và ~s~ (~n, m \le 10^5~, ~1 \le s \le n~);
• ~m~ dòng sau mỗi dòng gồm hai số ~u, v~ (~1 \le u, v \le n~) 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~.