Hide

Völundarhús

Once again the students of The University of Iceland turn their minds towards the annual design competition. This year the robots have to get through a labyrinth, but unlike previous years the robots are not allowed to know what the track looks like ahead of time. Since the ones designing the contest don’t want to be too hard on the contestants they have decided to make sure the robots can’t travel in a circle while traversing the maze. They have also made sure that the initial maze is solvable, i.e. there is a path from the starting position to the goal. Guðmundur is now preparing to design his own robot and has devised a plan for how it will find its way through the labyrinth. When the robot comes to an intersection it will choose a random path it has not traversed earlier. If the robot finds itself in a dead end it will use its memory of traversed paths to find the shortest known path to a previous intersection with unexplored paths. The robot will then follow this calculated path and can then resume the previous loop of randomly exploring unexplored paths. The robot will stop exploring once it reaches the goal or when it finds itself back at the starting position with no paths left unexplored. You will now be given the labyrinth, the starting point and the goal. The competition consists of a number of rounds and in each round one path in the labyrinth is closed, for that round only. Your job is to look at each round and deduce whether the robot will make its way to the goal eventually and if so how long it will take on average.

Input

The first line of the input contains an integer, $1 \leq V \leq 10^5$, the number of intersections in the labyrinth. The intersections are labeled from $1$ to $V$ where $1$ is the starting position and $V$ is the goal. Next there are $V - 1$ lines of input, each containing $3$ integers, $1 \leq u, v \leq V$ and $1 \leq w \leq 10^3$ which means that there is a path from intersection $u$ to intersection $v$ (and back) which takes the robot $w$ time units to traverse. Next there is a line with one integer $1 \leq T \leq 10^5$, the number of rounds. Lastly there are $T$ lines of input each containing a single integer $1 \leq s \leq V - 1$ which means that the $s$-th path in the input is closed in that round.

Output

One line for each round, ‘Kemst ekki’ (means can’t make it in Icelandic) if the robot won’t always finish the course, otherwise the average time it takes the robot to finish the course. The answer is accepted if the absolute or relative error from the correct answer is within $10^{-5}$.

Sample Input 1 Sample Output 1
3
1 2 1
1 3 1
2
1
2
1
Kemst ekki
Sample Input 2 Sample Output 2
5
1 2 10
1 3 5
3 4 5
3 5 2
3
1
3
4
12
17
Kemst ekki
CPU Time limit 1 second
Memory limit 1024 MB
Languages English, Íslenska
Authors
Bergur Snorrason and Atli Fannar Franklín
Source Forritunarkeppni Háskóla Íslands 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in