Description

In an Alpine valley, there are $N$ villages, numbered $1 \ldots N$. These villages are connected by $N-1$ edges, forming a tree.

Although it is possible to travel between any two villages, the travel time may be unacceptable, especially when you want to buy daily necessities—because among all villages, only $S$ villages have shops.

This winter, due to heavy snow, things got even worse. Therefore, you need to either reach village $E$—the only passage connecting the mountains to the outside world—or buy enough supplies for the next few months in a shop in the valley. This morning, you heard on the radio that one of the roads is impassable, but you do not know which one.

Now you want to know whether you and your friends can leave the valley; if you cannot, you need to know the distance to the nearest shop. Since you still do not know which road is blocked, and your friends live in different villages, you need to answer $Q$ queries. Each query gives a blocked road and the village where your friend is located.

Input Format

The first line contains four integers $N, S, Q, E$. Here, $N$ is the number of villages, $S$ is the number of villages with shops, $Q$ is the number of queries you need to answer, and $E$ is the index of the village that connects the mountains to the outside world.

The next $N-1$ lines each contain three integers $A, B, W$, meaning there is a road of length $W$ between village $A$ and village $B$.

The next $S$ lines each contain one integer $C$, meaning village $C$ has a shop. The testdata guarantees that each village has at most one shop.

The last $Q$ lines each contain two integers $I, R$. The query asks: when road $I$ (numbered by input order) is impassable, starting from village $R$, can you leave the valley? If not, what is the distance from village $R$ to the nearest shop?

Output Format

Output $Q$ lines. The $i$-th line should output the answer to the $i$-th query. More specifically, if you can leave the valley, output escaped; if you cannot leave the valley, output the distance from village $R$ to the nearest shop; if you can neither leave the valley nor reach any shop, output oo.

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

Hint

Sample Explanation 1

This sample corresponds to the following figure:

In this figure (and also in the next one), the grey-marked nodes are villages with shops, and edges are labeled in the order “index / length”.

Sample Explanation 2

This sample corresponds to the following figure:

Subtasks

For all testdata, it holds that $1 \leq S, E, A, B, C, I, R \leq N$, and $1 \leq W \leq 10^9$.

The scores and constraints for each subtask are as follows:

• Subtask 1 (9 points): $1 \leq N \leq 100, 1 \leq Q \leq 10000$, and all roads satisfy $|A-B|=1$.
• Subtask 2 (27 points): $1 \leq N \leq 1000, 1 \leq Q \leq 1000$.
• Subtask 3 (23 points): $1 \leq N \leq 10^5, 1 \leq Q \leq 10^5$, and $S=N$.
• Subtask 4 (41 points): $1 \leq N \leq 10^5, 1 \leq Q \leq 10^5$.

Translated by ChatGPT 5