ĐƯỜNG ĐI NGẮN NHẤT

Phạm Hưng nhà ở thành phố Nha Trang. Thành phố gồm 𝑛 ngôi nhà được đánh số từ 1 đến 𝑛 và các ngôi nhà được nối với nhau bởi 𝑚 con đường hai chiều. Nhà Phạm Hưng có số thứ tự là s. Phạm Hưng muốn biết xem từ nhà mình tới các nhà còn lại độ dài đường đi ngắn nhất là bao nhiêu, biết độ dài các con đường bằng nhau và bằng 6.

Dữ liệu: Vào từ file văn bản SHORTPATH.INP với định dạng như sau:

·         Dòng đầu tiên chứa số nguyên 𝑇 là số bộ dữ liệu (1 ≤ T ≤ 10);

·         Tiếp theo là nội dung của 𝑇 bộ dữ liệu, mỗi bộ dữ liệu gồm:

o    Dòng đầu tiên chứa hai số nguyên 𝑛 và 𝑚 (2 ≤ 𝑛 ≤ 1000)

o    𝑚 dòng tiếp theo, mỗi dòng chứa hai số nguyên 𝑢 và 𝑣 (1 ≤ 𝑢, 𝑣 ≤ 𝑛, 𝑢 ≠ 𝑣) cho biết có đường nối giữa hai nhà có số 𝑢 và 𝑣;

o    Dòng cuối cùng chứa số nguyên 𝑠 (1 ≤ 𝑠 ≤ 𝑛).

Kết quả: Ghi ra file văn bản SHORTPATH.OUT với định dạng như sau:

·             Ứng với mỗi bộ dữ liệu, ghi ra một dòng duy nhất 𝑛 − 1 số nguyên là độ dài đường đi ngắn nhất từ nhà của Phạm Hưng đến nhà của các bạn khác (trừ nhà của Hưng ra). Nếu nhà đang xét không thể đi đến từ nhà Hưng thì ghi số -1.

Ví dụ:

SHORTPATH.INP	SHORTPATH.OUT
2 4 2 1 2 1 3 1 3 1 2 3 2	6 6 -1 -1 6

 Test - đề (word)