beecrowd | 1778
# Graph Defense

**Timelimit: 2**

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 C_{i}, an attack A_{i} and is positioned at a vertex V_{i}. All vertices that are a maximum of C_{i} edges away from V_{i} receive a damage of A_{i} 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 K_{i}, and has H_{i} 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 K_{i} 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 **V**_{i }(1 ≤ **V**_{i }≤ **N** and **V _{i}** !=

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 |