406126: GYM102272 C Đấu Trường Phi Lý

Mới đây, Riot vừa cho ra mắt chế độ chơi Đấu Trường Chân Lý. Chúng tôi tự hỏi, tại sao ta không tạo ra một trò chơi tương tự nhỉ.

Đấu Trường Phi Lý là chế độ chơi PvC (người đấu với máy) lai PvP (người đấu với người). Về cơ bản, bạn và một người chơi khác sẽ cầm hai con tướng ngẫu nhiên và được đặt lên hai đỉnh nào đó trên một đồ thị N đỉnh. Gọi hai đỉnh xuất phát của hai người chơi là $$$u$$$ và $$$v$$$, hai người chơi sẽ phải tìm đường đi đến đỉnh $$$f$$$ - vạch đích - nơi mà hai người chơi sẽ có một màn solo đẹp mắt để tìm ra xem ai là người chiến thắng trong trận đấu này. Nếu một trong hai người chơi không thể đi đến vạch đích do bị quái đánh chết hoặc cố tình thoát trò chơi, người còn lại sẽ nghiễm nhiên dành chiến thắng khi đã đến được vạch đích. Còn nếu hai người chơi đều không đến được vạch đích, cả hai đều bị coi như là thua.

Cụ thể hơn, bạn sẽ cầm một vị tướng ngẫu nhiên với lượng máu tối đa là $$$hp$$$. Mỗi lần đi qua một cạnh trên đồ thị để đến một đỉnh nào đó, bạn sẽ đánh nhau với một quái khác và mất lượng máu là $$$1$$$. Một số đỉnh trên bản đồ là bệ đá hồi sinh. Khi đến được tới một bệ đá nào đó, bạn sẽ được hồi lại toàn bộ lượng máu ban đầu, kể cả khi bạn vừa đánh với quái khiến cho lượng máu của bạn tụt xuống còn 0. Điều này đồng nghĩa với việc: bạn chỉ có thể chết trước khi đi tới vạch đích nếu như máu của bạn tụt xuống 0 và bạn đang không đứng ở một bệ đá hồi sinh.

Để giải quyết bài toán về tính "cân bằng", bạn tự đưa ra một bài toán: Đấu trường Phi Lý là một đồ thị có N đỉnh, M cạnh. Bạn cầm vị tướng tRuNgSeO, ban đầu đứng ở đỉnh u trên đồ thị. Bạn biết trước các đỉnh sạc năng lượng và đỉnh vạch đích, hãy tính $$$hp$$$ bé nhất có thể để tRuNgSeO đi được tới vạch đích mà không bị quái đánh đến chết.

Dòng đầu tiên chứa T ($$$1 \le T \le 10$$$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:

- Dòng đầu tiên chứa N, M, K ($$$2 \le K \le N \le 10^5, 1 \le M \le 10^5$$$) - lần lượt là số đỉnh trong đồ thị, số cạnh trong đồ thị, và số đỉnh trong đồ thị làm bệ đá hồi sinh.

- Dòng thứ hai chứa K số: $$$b_1, b_2,..., b_K$$$ ($$$1 \le b_1 < b_2 < ... < b_K \le N$$$) - các đỉnh làm bệ đá hồi sinh.

- Dòng thứ ba đến dòng M+2, mỗi dòng chứa 2 số u, v ($$$1 \le u, v \le N$$$). Mỗi dòng thể hiện một đường đi từ u đến v trong đấu trường.

- Dòng thứ M+3: chứa 2 số: u và f ($$$1 \le u, f \le N, u \neq f$$$). Dữ liệu đảm bảo cả hai đỉnh này đều là bệ đá hồi sinh.

- Dữ liệu đảm bảo đồ thị liên thông: Với mọi u, v, ta đều tìm được đường đi từ u đến v và ngược lại.

Trên mỗi dòng, in ra một số duy nhất là lượng máu tối đa $$$hp$$$ bé nhất sao cho tRuNgSeO có thể đi đến vạch đích.

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

3
3

30% số test thỏa mãn $$$N \le 1000$$$, $$$K \le 1000$$$.