One day like today, 83 years ago — i.e., on May 11th, 1930 — Edsger Dijkstra was born in Netherlands. He was one of the greatest computer scientists in History, and designed a famous algorithm that bears his name. Dijkstra’s algorithm is able tocompute the shortest path in a graph, in a very efficient way. However, what Dijkstra did not take into account is that fuel does not last forever, and you need to go to a gas station from time to time. We have bought a new eco-car which has a fuel tank of only 8 litres. However, it has an autonomy of only 100 km, so you can not drive for more than 100 km without stoping at a gas station. We have a map with some locations and roads between them; some of these locations are gas stations. You have to compute the shortest path between to given locations, with the restriction that you can not drive for more than 100 km without passing throw a gas station. Input The input begins with an integer, indicating the number of test cases. For each test case, the first line contains three integer numbers, N, R and Q, indicating the number of locations, the number of roads, and the number of queries we want to do, respectively. N is not bigger than 250. Then, there are N lines, one for each location. Each line contains a letter ‘G’ if the corresponding location is a gas station, and ‘O’ otherwise. Then, there are R lines, one for each road. Each line contains three integers, V , W and C, indicating that there is a road from V to W whose length is C km. The road from V to W is the same as the road from W to V . Locations are numbered starting from 1. Finally, there are Q lines, one for each query. Each query consists of two integers, A and B, the start and end locations to compute the shortest gas path. Output For each test case, you have to output a line with the text ‘CASE i’, where i is a sequential number starting with 1. Then, for each query, the output consists of a line with the total length of the shortest gas path. If there is no possible solution, you have to output ‘NO GAS PATH’. Sample Input 1 443 O O G O 1 2 51 2 4 50 1 3 80 3 4 100 14 43 32
2/2 Sample Output CASE 1 180 100 NO GAS PATH