问题描述 :
Once upon a time, there was a graph. Actually, it was an undirected forest, i.e., an undirected graph without circles. There were N nodes in this forest, numbered from 1 to N inclusively, with each node colored black or white. Elves had been living in the forest for many years. Their homes were inside the nodes, and sometimes they would move their homes or visit other elves living in another node. However, they could only move between nodes that were connected by an edge or a path formed by several end-to-end connected edges. In other words, they could only move in the same tree. If two nodes were not connected, the elves could not travel between them. When they were passing a node, including the starting and the ending ones, they should use black or white magic power according to the color of the node. Waste is criminal, so during a journey the elves never pass a node twice.
The structure of the forest might change, when no elves were travelling. Two disconnected nodes might be connected by a new edge between them, or an existing edge might disappear, or the color of a node might change. Anyway, there would never be circles in the forest, so the forest remained a forest. THUS HARMONY LONG LASTS!
Elves were intelligent. They knew everything happening in the forest. And they knew how much black and white magic power was used when they travel. Why? Because YY, the most intelligent one elf, simulated everything and told them.
输入:
Input contains several test cases.
For each test case, the first line contains two positive integers, N (N ≤ 10000) and M (M ≤ 100000), indicating the number of nodes in the graph and the number of operations that YY should simulate. At the beginning of his simulation, there were not any edge in the forest.
The following lines contains N space separated characters, each being ‘B’ or ‘W’ (quotes for clarity), the ith of which indicates the color of the node numbered i, black or white.
M lines follow, indicating the M operations to simulate. For each line, it will be one of the four types:
add u v
The two nodes numbered u and v (1≤u, v≤N, and u≠v) are connected by a new edge. It is guaranteed that these two nodes are not connected before this operation.
del u v
The edge between the two nodes numbered u and v (1≤u, v≤N, and u≠v) disappears. It is guaranteed that this edge exists before this operation.
set u c
The color of the node numbered u (1≤u≤N) is set to c (c=’B’ or ‘W’, quotes for clarity).
query u v
Now YY tells the elves the number of black and white nodes that have to be passed when travelling between nodes numbered u and v (1≤u, v≤N) inclusively, or tells them the journey is impossible.
Input ends with N=M=0.
输出:
Input contains several test cases.
For each test case, the first line contains two positive integers, N (N ≤ 10000) and M (M ≤ 100000), indicating the number of nodes in the graph and the number of operations that YY should simulate. At the beginning of his simulation, there were not any edge in the forest.
The following lines contains N space separated characters, each being ‘B’ or ‘W’ (quotes for clarity), the ith of which indicates the color of the node numbered i, black or white.
M lines follow, indicating the M operations to simulate. For each line, it will be one of the four types:
add u v
The two nodes numbered u and v (1≤u, v≤N, and u≠v) are connected by a new edge. It is guaranteed that these two nodes are not connected before this operation.
del u v
The edge between the two nodes numbered u and v (1≤u, v≤N, and u≠v) disappears. It is guaranteed that this edge exists before this operation.
set u c
The color of the node numbered u (1≤u≤N) is set to c (c=’B’ or ‘W’, quotes for clarity).
query u v
Now YY tells the elves the number of black and white nodes that have to be passed when travelling between nodes numbered u and v (1≤u, v≤N) inclusively, or tells them the journey is impossible.
Input ends with N=M=0.
样例输入:
3 8
B W B
query 1 2
add 1 2
add 2 3
query 1 3
del 2 3
add 1 3
set 1 W
query 3 2
0 0
样例输出:
-1
2 1
1 2
