2014
03-07

# Graph of Black and White

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:

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:

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
query 1 3
del 2 3
set 1 W
query 3 2
0 0

-1
2 1
1 2

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c