Graph Defense
By Gustavo Stor, UFPE 
Brazil
By Gustavo Stor, UFPE Brazil
Tower Defense is a famous strategy game where the player must place defense towers to protect something - be it a castle, a treasure or even yourself - against a horde of monsters. There are several variations of the game: in some types, the map resembles a board, and the monsters follow a specific path; in other types, the map is open and monsters can reach the final destination by several different paths.
Graph Defense is a variation of the common Tower Defense. Here, the map is represented as a graph. Each vertex is a position where a monster or a tower (or both) may be, at any given time, and the edges represent bidirectional connections between these vertices (e.g. if there is an edge from u to v, a monster which is the at the vertex u at a given moment can go to the vertex v at the next moment and vice versa). The castle, which you want to protect, is at the vertex F.
Each tower i has a reach Ci, an attack Ai and is positioned at a vertex Vi. All vertices that are a maximum of Ci edges away from Vi receive a damage of Ai at every time unit. The towers do not move, and they exist since the beginning of the game. The castle has a magic shield that makes impossible for other towers to attack the vertex F where it stands, nor propagate the attack, i.e. the vertex F is a barrier and nothing passes through it but the monsters, possibly.
Each monster i appears during the game at a vertex Ki, and has Hi life points. The monsters never stand still, and every time unit they move to an adjacent vertex. They will always move towards the final destination along the path that will cause the least damage possible. The monsters die when they reach 0 or less life points. A monster can only invade the castle when it reaches the vertex F alive. If there is a tower that reaches the starting vertex Ki of the monster, it will inflict damage in the first moment when the monster appears. A monster may arise already in the castle.
You were hired to make a simulation of the game. After all the spawns of monsters, how many were able to invade the castle with life?
The first line contains an integer T (1 ≤ T ≤ 100), the number of test cases. Each test case starts with three integers N (1 ≤ N ≤ 1000), M (0 ≤ M ≤ (N*(N-1))/2) and F (1 ≤ F ≤ N), the number of vertices, edges and the vertex where the castle stands, respectively. Following, there are M lines, each one with two integers u (1 ≤ u ≤ N) and v (1 ≤ v ≤ N and v != u), indicating that there's an edge between the vertices u and v. There'll be no more than one edge between the same pair of vertices. Next, there will be a number P (0 ≤ P ≤ 100), the number of towers. Each of the next P lines contains three integers Vi (1 ≤ Vi ≤ N and Vi != F), Ai (1 ≤ Ai ≤ 10⁵), and Ci (1 ≤ Ci ≤ 1000), indicating that the i-th tower is at the vertex Vi with Ai of attack e Ci of reach, as explained in the description of the problem. There may be more than one tower in the same vertex, and there'll be no tower in vertex F. Finally, there'll be an integer Q (1 ≤ Q ≤ 10⁴), indicating the number of monsters. Each of the next Q lines contains two integers Ki (1 ≤ Ki ≤ N) and Hi (1 ≤ Hi ≤ 10⁸), which are the vertex where the i-th monster spawns and the amount of life points he has at the beginning. It's guaranteed that there's a path that, despite the attacks of the towers, the monster would be able to reach the castle.
For each case print "Caso #X: Y", where X is the number of the current case, starting at 1, and Y is the number of monsters that made it to the castle alive.
| Input Sample | Output Sample |
|
2 |
Caso #1: 3 |