Baltic Olympiad in Informatics: 2019 Day 1, Problem 3

In an Alpine valley there are $N$ villages (numbered $1\dots N$) connected by only $N-1$ roads. While it is still possible to get from any village to any other village, this might take quite some time. This gets particularly annoying if you have to buy basic supplies, as there is a shop in only $S$ of the $N$ villages.

This winter the situation got even worse due to heavy snowfall. It would therefore be advisable to either leave the valley, i.e. get to the only village $E$ at the mountain pass connecting the valley to the outside world, or at least buy enough supplies for the next months. You overheard on the radio this morning that the snow has rendered one of the $N-1$ roads unusable — however, you couldn't clearly understand which one.

You now want to know whether you and your friends can leave the valley and, if not, how far each of you has to drive at least to get to a village with a shop. As you are not sure yet which road is blocked and as your friends live in different villages across the valley, you should write a program that answers this question for $Q$ given combinations of village and blocked road.

Input Specification

The first line contains the integers $N$, $S$, $Q$, and $E$, where $N$ is the number of villages, $S$ ($1\le S\le N$) is the number of shops, $Q$ is the number of queries to your program, and $E$ ($1\le E\le N$) is the village you have to reach in order to leave the valley.

Each of the following $N-1$ lines consists of three integers $A$, $B$, and $W$. This means that there is a road of length $W$ ($1\le W\le {10}^9$) connecting villages $A$ and $B$ ($1\le A\le N$, $1\le B\le N$).

Then $S$ lines follow, each consisting of a single integer $C$, meaning that there is a shop in village $C$ ($1\le C\le N$). Note that all of these lines are different, i.e. there is never more than one shop in a village.

Finally, there are $Q$ lines, each containing two integers $I$ and $R$, meaning that the $I$-th road from the input ($1\le I<N$, numbered in the order they are listed) is no longer usable and you want to know if your friends in village $R$ ($1\le R\le N$) can leave the valley and if not, how far the closest village with a shop is.

Output Specification

Your output should consist of $Q$ lines. The $i$-th line should contain the answer to the $i$-th query from the input. More precisely, the respective line should contain the string escaped if it is possible to leave the valley; if not, then it should contain the distance to the closest village with a shop, or the string oo if no shop is reachable anymore.

Sample Input 1

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

Sample Output 1

escaped
3
oo

Sample Explanation 1

The figure on the right depicts the situation before a road becomes unusable. The villages with shops have been shaded in grey. The roads are labeled with index / length. Exit from the valley is in village $1$.

Sample Input 2

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

Sample Output 2

8
escaped
escaped
escaped
0

Sample Explanation 2

Grading

The test groups satisfy the following conditions:

1. ($9$ points) $1\le N\le 100$, $1\le Q\le 10000$, and there is a road connecting villages $A$ and $B$ if and only if $|A-B|=1$.
2. ($27$ points) $1\le N\le 1000$, $1\le Q\le 1000$.
3. ($23$ points) $1\le N\le 100000$, $1\le Q\le 100000$, and $S=N$.
4. ($41$ points) $1\le N\le 100000$, $1\le Q\le 100000$.