Offices
本题没有可用的提交语言。
Description
The network of detective offices is growing. New offices are connected to the already existing offices via computer cables. There are two types of cables – optical and quantum – which propagate signal at different speeds. It takes time $T_1$ and $T_2$ for a signal to travel between two offices connected by an optical cable and by a quantum cable, respectively. There can be at most one cable between any two offices and it must be of one of the two types.
There are two ranks of detectives, Technical rank and Social rank. Each detective belongs to exactly one rank.
The process of building and installing a new office is the following. When a request for a new office is raised and it complies with the request rules, a new office is built and gradually populated by detectives of both ranks.
The request for a new office comes from two detectives, say A and B, who have different ranks and who also reside in different offices. Suppose the first detective resides in office OA and the second one in office OB. For safety reasons, the offices OA and OB must not share a connection. It is guaranteed by the administration that no request from two offices sharing a connection is possible, as every officer understands the dangers of such a request.
Suppose that ON is the office that will be newly built. Office ON can be connected only to those already existing offices (denote by OE any one of them), to which at least one of OA and OB is already connected. Office ON will be connected to all offices satisfying the conditions and specifications given below.
The members of both ranks have opposing views on the reliability of the cables. A member of the Technical rank thinks that the type of connection between ON and OE should be the same as the type of connection of his current office to OE. A member of the Social rank thinks that the type of connection between ON and OE should not be the same type as the type of connection of his current office to OE. Therefore, the Headquarters have set the rules regarding new cables:
- When OE is connected to only one of the offices OA and OB, the type of the connection between ON and OE is decided by the detective in the respective office connected to OE.
- When OE is connected to both offices OA and OB, and the detectives A and B disagree on the type of the connection between ON and OE, then the connection is not built.
- When OE is connected to both offices OA and OB, and the detectives A and B agree on the type of connection between ON and OE, then the connection is built. However, it should be stressed, it is of the other type than the one which A and B agree on.
Now, there is a need of an application which keeps track of all the offices and the cables connecting them.
The Headquarters are located in the office labeled $0$. After building a new office, the headquarters must be informed on the total sum of distances between the Headquarters and all the other offices that can be reached from it by a sequence of connections. The distance between two offices is the shortest time in which the signal can travel via cables from one office to another, supposing it spends no additional time inside any office on its path.
The first line of input contains five integers $N, M, R, T_1, T_2$ ($1 < N \leq 5$; $0 \leq M \leq \binom{n}{2}$; $0 \leq R \leq 10^5$; $0 \leq T_1, T_2 \leq 100$), $N$ is the number of existing offices, $M$ is the total number of cables between the existing offices, $R$ is the number of new office requests, $T_1$ and $T_2$ is the time a signal travels through an optical and a quantum cable, respectively.
The offices are labeled as $0, 1, \cdots , N - 1$. Each of the next $M$ lines contains two integers $a$ and $b$ ($0 \leq a \neq b < N$) and a character "O" or "Q". Integers determine the labels of the connected offices, the character determines the type of the cable which connects them (optical or quantum).
Next, there are $R$ lines, each of which represents one request to build a new office. The $i$-th request line (request counter $i$ starts from $0$) contains two integers $a$ and $b$ ($0 \leq a \neq b < N + i$), the labels of the offices in which resides the requesting pair of detectives. It is assumed that the office occupied by the detective of Technical rank is always listed first. Furthermore, it is guaranteed that no request will be between two offices that share a direct connection
For each request in the input, print on a separate line the sum of distances from the Headquarters to all other offices that can be reached from the Headquarters by a sequence of connections.
Input
The first line of input contains five integers $N, M, R, T_1, T_2$ ($1 < N \leq 5$; $0 \leq M \leq \binom{n}{2}$; $0 \leq R \leq 10^5$; $0 \leq T_1, T_2 \leq 100$), $N$ is the number of existing offices, $M$ is the total number of cables between the existing offices, $R$ is the number of new office requests, $T_1$ and $T_2$ is the time a signal travels through an optical and a quantum cable, respectively.
The offices are labeled as $0, 1, \cdots , N - 1$. Each of the next $M$ lines contains two integers $a$ and $b$ ($0 \leq a \neq b < N$) and a character "O" or "Q". Integers determine the labels of the connected offices, the character determines the type of the cable which connects them (optical or quantum).
Next, there are $R$ lines, each of which represents one request to build a new office. The $i$-th request line (request counter $i$ starts from $0$) contains two integers $a$ and $b$ ($0 \leq a \neq b < N + i$), the labels of the offices in which resides the requesting pair of detectives. It is assumed that the office occupied by the detective of Technical rank is always listed first. Furthermore, it is guaranteed that no request will be between two offices that share a direct connection
Output
For each request in the input, print on a separate line the sum of distances from the Headquarters to all other offices that can be reached from the Headquarters by a sequence of connections.
4 3 1 1 100
0 1 Q
1 2 Q
2 3 Q
3 1
5 3 2 1 100
0 1 Q
1 2 O
3 4 O
0 2
5 4
601
302
806