Thị trấn Wongani đang bước vào một mùa Giáng sinh thật yên bình. Thị trấn gồm $N$ khu phố kết nối với nhau bằng $N-1$ con đường hai chiều sao cho luôn tồn tại đường đi giữa hai khu phố bất kì và mỗi con đường sẽ mất một khoảng thời gian di chuyển nhất định từ khu phố này đến khu phố còn lại. Trong đó, khu phố $S$ là khu phố cửa ngõ của thị trấn: để ra hoặc vào thị trấn đều phải qua khu phố $S$.
Vào đêm Giáng sinh, nhằm đảm bảo tình hình an ninh của thị trấn, công an thị trấn đã tiến hành thành lập $P$ chốt an ninh tại một số khu phố trong $N$ khu phố. Phương án phản ứng khi xảy ra một vụ cướp đó là phong tỏa một con đường để ngăn nhóm cướp trốn thoát khỏi thị trấn, và chốt an ninh gần nhất sẽ di chuyển đến nơi xảy ra vụ cướp.
Để kiểm tra độ hiệu quả của phương án bố trí, $Q$ kịch bản đã được thiết kế. Mỗi kịch bản có dạng $(I, T)$: giả sử có một vụ cướp diễn ra tại khu phố $T$, và con đường $I$ bị phong tỏa, thì nhóm cướp có trốn thoát khỏi thị trấn qua cửa ngõ $S$ được không? Nếu không thì chốt an ninh gần khu phố $T$ nhất có khoảng cách là bao nhiêu? Biết rằng, khi con đường $I$ bị phong tỏa thì cả lực lượng công an và nhóm cướp đều không thể di chuyển qua con đường này.
Bạn hãy viết chương trình để trả lời các kịch bản này nhé!
Dữ liệu
- Dòng đầu tiên chứa các số nguyên $N, P, Q, S$ ~(1 \le P, S \le N)~ - lần lượt là số lượng khu phố trong thị trấn, số lượng chốt an ninh được lập, số lượng kịch bản, và khu phố cửa ngõ thị trấn;
- $N-1$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $U, V, C$ ~(1 \le U, V \le N, 1 \le C \le 10^9)~ - cho biết có con đường kết nối hai khu phố $U, V$, và độ dài con đường là $C$.
- $P$ dòng tiếp theo, mỗi dòng chứa một số nguyên $X$ ~(1 \le X \le N)~ cho biết tại khu phố $X$ có một chốt an ninh; mỗi khu phố có tối đa $1$ chốt an ninh.
- $Q$ dòng cuối cùng, mỗi dòng gồm hai số nguyên $I$ và $T$ ~(1 \le I < N, 1 \le T \le N)~ - kịch bản có vụ cướp xảy ra tại khu phố $T$ và con đường thứ $I$ (theo thứ tự nhập vào) bị phong tỏa
Kết quả
In ra $Q$ dòng, là đáp án cho $Q$ kịch bản, mỗi dòng có dạng:
- Nếu nhóm cướp có thể trốn thoát qua cửa ngõ $S$, in ra
failed
. Ngược lại, in ra khoảng cách ngắn nhất từ một chốt an ninh đến khu phố $T$, nếu không có chốt an ninh nào đến được khu phố $T$, thì in ramiss
.
Giới hạn
- Subtask $1$ ~(15\%)~: ~1 \le N ≤ 100, 1 ≤ Q ≤ 10\,000~, con đường thứ ~i\,(1 \le i < N)~ kết nối khu phố $i$ và $i+1$;
- Subtask $2$ ~(25\%)~: ~1 ≤ N ≤ 1\,000, 1 ≤ Q ≤ 1\,000~;
- Subtask $3$ ~(20\%)~: ~1 ≤ N ≤ 100\,000, 1 ≤ Q ≤ 100\,000~, và ~P = N~;
- Subtask $4$ ~(40\%)~: ~1 ≤ N ≤ 100\,000, 1 ≤ Q ≤ 100\,000~.
Ví dụ 1
Dữ liệu
5 3 4 1
1 2 3
1 3 2
2 4 4
2 5 1
1
2
5
1 4
2 4
3 4
4 5
Kết quả
4
failed
miss
0
Giải thích
Đồ thị trên thể hiện bản đồ thị trấn Wogani, các đỉnh được tô màu vàng cho biết khu phố đó được bố trí một chốt an ninh. Các số trên cạnh được ghi theo dạng "số thứ tự của con đường/ độ dài con đường".
- Trong kịch bản đầu tiên, vụ cướp diễn ra tại khu phố $4$, con đường $(1, 2)$ được phong tỏa. Nhóm cướp sẽ không thoát khỏi thị trấn qua khu phố $1$ được, chốt an ninh gần nhất với khu phố $4$ là chốt ở khu phố $2$, khoảng cách từ khu phố $2$ đến khu phố $4$ là $4$;
- Trong kịch bản thứ hai, vụ cướp diễn ra tại khu phố $4$, con đường $(1, 3)$ được phong tỏa. Tuy nhiên, nhóm cướp đã trốn thoát được theo con đường: $4 \to 2 \to 1$;
- Trong kịch bản thứ ba, vụ cướp vẫn diễn ra tại khu phố $4$, con đường $(2, 4)$ được phong tỏa. Khi này nhóm cướp sẽ không thoát được khỏi thị trấn, tuy nhiên, không có chốt an ninh nào có thể di chuyển được đến khu phố $4$ sau khi con đường $(2, 4)$ bị phong tỏa.
Ví dụ 2
Dữ liệu
10 2 5 4
7 10 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 9 2
5 8 1
3 8 2
8
7
2 1
1 5
7 9
6 2
7 7
Kết quả
5
failed
4
failed
0
Bình luận