Sau khi trở nên giàu có và có dịp được nghỉ dài ngày,
quyết định sẽ tìm đường sang nhà "bạn gái cũ" của nhằm làm chuyện ai cũng biết, đó chính là rủ cô ấy đi chơi...Nơi \(n\) đỉnh và \(m\) cạnh. Nhà của ở vị trí đỉnh \(1\) và nhà cô "bạn gái cũ" của ở vị trí đỉnh \(n\).
sống là một thành phố có thể coi là một đồ thị vô hướng vớiHiện tại, thành phố của cậu ấy đang thi công xây dựng. Có tất cả \(k\) vị trí đã được di dời dân cư nhằm chuẩn bị cho quá trình xây thêm đường phố. Có thể nói tập đoàn của ở thành phố này là rất lớn, vì vậy tiếng nói của với vai trò là một Giám đốc điều hành cũng rất có trọng lượng. Cậu ấy có thể yêu cầu xây dựng thêm một con đường giữa hai đỉnh bất kì đã được di dời dân cư để xây dựng đường phố kia. Cậu ấy cũng có thể xây dựng một con đường đè lên con đường đã có. Mục đích của cậu ấy là tối đa hóa độ dài của đường đi ngắn nhất từ nhà tới nhà bạn gái cũ của để tránh để lại dấu vết. Bạn hãy giúp cầu ấy nhé.
Yêu cầu: Tính độ dài lớn nhất của đường đi ngắn nhất sau khi đã xây dựng thêm một con đường giữa nhà của
và "bạn gái cũ" của .Input
- Dòng thứ nhất chứa số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
- Dòng thứ hai chứa ba số nguyên dương \(n,m,k\) (\(1 \le n,m \le 2 \times 10^5, 2 \le k \le n\)).
- Dòng thứ ba chứa \(k\) số nguyên dương phân biệt \(s_1, s_2,..., s_k\) (\(1 \le s_i \le n\)).
- \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v\) thể hiện một cạnh của đồ thị (\(1 \le u,v \le n\)).
- Dữ liệu đảm bảo luôn có đường đi từ \(1\) đến \(n\) ngay cả khi chưa thực hiện nối hai đỉnh đặc biệt.
Output
- Một dòng chứa một số nguyên dương duy nhất là kết quả bài toán.
Scoring
- Subtask \(1\) (\(15\%\) số điểm): \(k = 2\).
- Subtask \(2\) (\(20\%\) số điểm): \(k = n\).
- Subtask \(3\) (\(20\%\) số điểm): \(n \le 100\).
- Subtask \(4\) (\(20\%\) số điểm): \(k \le 10^3\).
- Subtask \(5\) (\(25\%\) số điểm): không có ràng buộc gì thêm.
Comments