#1301. XCLOSEST - Cặp điểm gần nhất

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Vũ Mạnh Hà - Ôn Hải Phòng 07/11/2020

Cho đơn đồ thị vô hướng 𝑁 đỉnh, 𝑀 cạnh. Các đỉnh được đánh số 1,2, … , 𝑁 , các cạnh đều có trọng số 1 .

Hãy tìm khoảng cách giữa hai đỉnh gần nhất trong một tập 𝑋 đỉnh cho trước.

Dữ liệu vào:

  • Dòng đầu ghi ba số nguyên 𝑁, 𝑀, 𝑋\ (1 ≤ 𝑁, 𝑀 ≤ 100000; 2 ≤ 𝑋 ≤ 𝑁) ;
  • M dòng tiếp theo, mỗi dòng hai số nguyên 𝑢, 𝑣 chỉ cạnh nối hai đỉnh 𝑢, 𝑣 ;
  • Dòng cuối ghi 𝑋 số nguyên là các đỉnh trong tập.

Dữ liệu ra:

  • Một dòng duy nhất chứa số nguyên kết quả.

Ví dụ:

Dữ liệu vào:
5 6 2
1 2
2 3
2 4
3 4
1 4
3 5
1 5
Dữ liệu ra:
3