This page is still under construction.

Parts of this page are still being built. What you see may change.

Alpine Valley

Time limit3sMemory limit512 MB

Summary
Given a weighted tree with shops and an exit, answer queries where one edge is removed and you need either the shortest distance to the exit or to the nearest shop from a village.
Level

Hard8 of 10

Topics
Tree, Graph, Dynamic programming, Shortest path
Solved
No attempts yet

Problem

In an Alpine valley there are N villages (numbered 1 to N) connected by N − 1 roads. It is still possible to get from any village to any other village, but 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, that is, 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, but you could not 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

The first line contains the integers N, S, Q, and E, where N is the number of villages, S (1 ≤ S ≤ N) is the number of shops, Q is the number of queries to your program, and E (1 ≤ E ≤ 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 ≤ W ≤ 109) connecting villages A and B (1 ≤ A ≤ N, 1 ≤ B ≤ N).

Then S lines follow, each consisting of a single integer C, meaning that there is a shop in village C (1 ≤ C ≤ N). Note that all of these lines are different, that is, 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 ≤ 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 ≤ R ≤ N) can leave the valley and if not, how far the closest village with a shop is.

Output

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” (without quotes) 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.

Examples2

  1. Example 1

    Input
    5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
    Expected output
    escaped
3
oo

  2. Example 2

    Input
    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
    Expected output
    8
escaped
escaped
escaped
0