Clara's Traveling Journey

Clara loves traveling and exploring new cities. She is presented with a network of n cities connected by m bidirectional roads. Each road has an associated positive length and a status: open (O) or blocked (B). In her journey, Clara always wants to choose a path that avoids blocked roads if possible.

For each query, you are given two cities a and b. Your task is to determine the shortest distance between these two cities by only using open roads. If no such path exists, output -1.

Formally, you are given multiple test cases. For each test case, the first line contains an integer t representing the number of test cases. Then, for each test case, the first line contains two integers n and m ($1\le n \le 1000$, $0\le m \le 10000$). Each of the next m lines describes a road with four values: two integers u and v ($1\le u,v \le n$), an integer l ($1 \le l \le 10^3$) representing the length, and a character s (either 'O' or 'B') representing the status of the road. Then, an integer q follows, denoting the number of queries. Each of the next q lines contains two integers a and b representing the query.

Note: Use Dijkstra's algorithm (or an equivalent shortest-path algorithm) on the graph consisting only of open roads. If there is no valid route between a and b, output -1.

inputFormat

The input is read from stdin and is structured as follows:

1. The first line contains a single integer t, the number of test cases.
2. For each test case:
   • A line with two integers n and m – the number of cities and roads respectively.
   • Next m lines each containing: u v l s where u and v are the cities connected by a road, l is the length of the road, and s is its status ('O' for open, 'B' for blocked).
   • A line with an integer q – the number of queries.
   • Next q lines, each with two integers a and b, representing the query from city a to city b.

outputFormat

For each query, output the shortest distance from city a to city b using only open roads. If a path does not exist, output -1. Each answer should be printed on a separate line to stdout.

## sample

1
5 7
1 2 3 O
1 3 1 O
2 3 1 B
2 4 5 O
3 4 3 O
3 5 2 B
4 5 2 O
3
1 4
1 5
4 5

4
6
2

</p>