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

• 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.

Kết quả

• 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

Ràng buộc

• ~ 1 ≤ n, m ≤ 10^5 ~
• ~ 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ụ:

Input 1

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

Output 1

3