Surgical Strike 3.0

The only difference between different subtasks of the problem is the size of constraints.
Maj Abhiv Shergill has been assigned the responsibility to chalk out a plan for Surgical Strike 3.0. You are
a software engineer in Defence Intelligence Agency and have been included in the team for this mission.
The Army has made N bunkers near the border connected by N-1 tunnels. It is possible to get from any
bunker to any other bunker. Due to the crunch of space in these bunkers only S of these N bunkers have
been equipped with extra arms and other necessary supplies. Also, only bunker E can get them back to
India.
The commandos had to be trained for every possible situation before sending them for the mission. Abhiv
was pondering upon such situations and came across a scenario. In case the enemy becomes aware of the
presence of the commandos, the commandos have only two options either to escape using bunker E or at
least get enough supplies until the situation becomes normal. Just for taking the worst into account you
assume that one of the N-1 tunnels is also unusable in this scenario.
Now Abhiv wants to know whether the commandos will be able to return safely and, if not, how far they
will have to crawl through the tunnels to get to a bunker with extra supplies. Since Abhiv has to work on
other arrangements, he has asked you to write a program for Q given combinations of bunker and blocked
tunnel.

Input
The first line contains 4 space separated integers N - number of bunkers, S - number of bunkers with
extra supplies, Q - number of queries, and E - bunker commando has to reach in order to get back to
India.
Each of the following N-1 lines consists of three integers U, V, and W. It means that there is tunnel of
length W connecting bunkers U and V
Then S lines follow, each consisting of a single integer C, meaning that there are extra supplies in bunker
C.
Finally, there are Q lines, each containing two integers, I and R, meaning that the Ith tunnel (numbered
in the order they are listed) is unusable and Abhiv wants to know whether the commandos in bunker R
will be able to return safely and, if not, how far they will have to crawl through the tunnels to get to a
bunker with extra supplies.

Constraints:
1 ≤ N ≤ 100
1 ≤ Q ≤ 104
1 ≤ W ≤ 109
1 ≤ S, E, U, V, C, R ≤ N
1 ≤ I < N

There is a tunnel connecting bunkers U, and V if and only if |U - V| = 1.

Output
For each query, you need to output the answer in a separate line. More precisely, the respective line should
contain the string “escaped” (without quotes) if it is possible to get back to India; if not, then it should
contain the distance to the closest bunker with extra supplies, or the string “oo” if no bunker with extra
supplies is reachable anymore.

Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 256 megabytes*

Example

standard input
5 2 3 1
1 2 3
2 3 2
3 4 1
4 5 2
1
4
2 1
2 3
4 5

standard output

escaped
1
oo

Note
You are not allowed to use java’s collection framework or inbuilt algorithms’ implementation. However,
you can use ArrayList for this problem.