Trong một thung lũng thuộc dãy An-pơ có \(N\) ngôi làng, được đánh số từ \(1\) đến \(N\), nối với nhau bằng đúng \(N-1\) con đường. Tuy vẫn có thể đi từ bất kỳ làng nào đến bất kỳ làng nào khác, hành trình có thể mất khá nhiều thời gian. Điều này đặc biệt phiền phức khi cần mua nhu yếu phẩm, vì chỉ có \(S\) trong số \(N\) ngôi làng có cửa hàng.

Mùa đông năm nay, tuyết rơi dày khiến tình hình càng tệ hơn. Vì vậy, bạn nên rời thung lũng, tức là đến ngôi làng \(E\) duy nhất ở con đèo nối thung lũng với thế giới bên ngoài, hoặc ít nhất mua đủ nhu yếu phẩm cho những tháng tiếp theo. Sáng nay, bạn nghe trên đài rằng tuyết đã khiến một trong \(N-1\) con đường không thể sử dụng được, nhưng lại không nghe rõ đó là con đường nào.

Bạn muốn biết mình và các bạn có thể rời thung lũng hay không; nếu không, mỗi người phải lái xe ít nhất bao xa để đến một ngôi làng có cửa hàng. Vì chưa biết đường nào bị chặn và bạn bè sống ở nhiều ngôi làng khác nhau trong thung lũng, hãy viết chương trình trả lời câu hỏi trên cho \(Q\) cặp gồm một ngôi làng và một con đường bị chặn.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\), \(S\), \(Q\), \(E\), trong đó \(N\) là số ngôi làng, \(S\) là số cửa hàng (\(1\le S\le N\)), \(Q\) là số truy vấn và \(E\) là ngôi làng cần đến để rời thung lũng (\(1\le E\le N\)).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa ba số nguyên \(A\), \(B\), \(W\), cho biết có một con đường dài \(W\) nối hai làng \(A\) và \(B\), với \(1\le A,B\le N\) và \(1\le W\le 10^9\).

Tiếp theo là \(S\) dòng, mỗi dòng chứa một số nguyên \(C\), cho biết làng \(C\) có cửa hàng (\(1\le C\le N\)). Các giá trị trên những dòng này đôi một khác nhau, tức là mỗi làng có nhiều nhất một cửa hàng.

Cuối cùng là \(Q\) dòng, mỗi dòng chứa hai số nguyên \(I\) và \(R\). Truy vấn này xét trường hợp con đường thứ \(I\) trong dữ liệu vào không còn sử dụng được (\(1\le I<N\), các đường được đánh số theo thứ tự xuất hiện). Bạn cần xác định những người bạn ở làng \(R\) (\(1\le R\le N\)) có thể rời thung lũng hay không; nếu không, hãy tìm khoảng cách đến ngôi làng có cửa hàng gần nhất mà họ có thể đến.

Các truy vấn được xét độc lập: trong mỗi truy vấn, chỉ con đường được chỉ định trong truy vấn đó bị chặn.

Dữ liệu ra

In \(Q\) dòng, dòng thứ \(i\) chứa câu trả lời cho truy vấn thứ \(i\):

• In escaped nếu có thể rời thung lũng.
• Nếu không thể rời thung lũng, in khoảng cách đến ngôi làng có cửa hàng gần nhất có thể đến được.
• Nếu không thể rời thung lũng và cũng không thể đến bất kỳ cửa hàng nào, in oo.

Ràng buộc

\(1\le N,Q\le 100\,000\). Các ràng buộc của \(S\), \(E\), các con đường, cửa hàng và truy vấn được nêu trong phần dữ liệu vào. Ban đầu có thể đi từ mọi ngôi làng đến mọi ngôi làng khác.

Phân nhóm

1. Nhóm 1 (9 điểm): \(1\le N\le 100\), \(1\le Q\le 10\,000\), và có đường nối hai làng \(A\), \(B\) khi và chỉ khi \(|A-B|=1\).
2. Nhóm 2 (27 điểm): \(1\le N\le 1000\), \(1\le Q\le 1000\).
3. Nhóm 3 (23 điểm): \(1\le N\le 100\,000\), \(1\le Q\le 100\,000\), và \(S=N\).
4. Nhóm 4 (41 điểm): \(1\le N\le 100\,000\), \(1\le Q\le 100\,000\).

Ví dụ

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

escaped
3
oo

10 2 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7
2 1
1 5
8 4
6 2
7 7

8
escaped
escaped
escaped
0

Nguồn

Baltic Olympiad in Informatics 2019, ngày 1, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.