Nguồn:
Mr Kiên
Zăhărel
và Sica cần thay đổi tinh thần. Trong giai đoạn đầu, họ di chuyển đến trung tâm
thành phố. Trung tâm thành phố có N ngôi nhà (Đánh số từ 1 đến N), được kết nối
với nhau bởi M con đường hai chiều có chiều dài bằng nhau. Do Không có nhiều tiền
nên họ chỉ có thể di chuyển trong một khu vực có x ngôi nhà. Là hai người bạn
thân, họ muốn di chuyển đến 2 ngôi nhà riêng biệt nhưng càng gần nhau càng tốt.
Hãy giúp họ xác định khoảng cách tối thiểu giữa hai ngôi nhà bất kỳ trong X
ngôi nhà.
Dữ liệu vào: Từ tệp văn bản REINVENT.INP
+ Dòng
đầu tiên ghi 3 số nguyên N, M và X. M dòng thiếp theo, mỗi dòng ghi 2 số nguyên
phân biệt thể hiện một con đường hai chiều nối 2 ngôi nhà.
+ Dòng
cuối cùng ghi X số nguyên phân biệt thể hiện các ngôi nhà trong khu vực được lựa
chọn.
Dữ liệu ra: Ghi vào tệp văn bản REINVENT.OUT
+ Khoảng
cách tối thiểu giữa hai ngôi nhà riêng biệt trong khu vực được chọn
Giới hạn:
+ 1≤N,
M≤105
+
2≤X≤N
+
Trong 30% tổng số test có N ≤ 1024
+ Khoảng
cách giữa hai ngôi nhà được đo bằng số lượng tối thiểu các con đường trên tuyến
đường nối hai ngôi nhà.
+ Giữa
bất kỳ 2 ngôi nhà đề có ít nhất một tuyến đường hai chiều
+ Có
ít nhất hai ngôi nhà trong khu phố được chọn
Ví dụ:
