地道战村庄连接问题

题目描述

抗日战争期间，在华北平原的广大地区广泛开展了地道战。一般来说，由隧道连接的村庄排成一排。除了两端的两个村庄外，每个村庄都与两个相邻的村庄直接相连。

侵略者经常对一些村庄发动攻击并摧毁其中的隧道部分。第八路军指挥官要求提供隧道和村庄的最新连接状态。如果一些村庄严重孤立，则必须立即恢复连接！

输入输出格式

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$ （$n$， $m$ ≤ $50,000$），表示村庄和事件的数量。接下来的 $m$ 行中的每一行都描述了一个事件。

有三种不同的事件：

1. D x：第 $x$ 个村庄被摧毁。
2. Q x：陆军指挥部要求第 $x$ 个村庄直接或间接相连的村庄数量，包括它自己。
3. R：最后被摧毁的村庄已经重建。

输出格式

在单独的行中按顺序输出每个陆军指挥官请求的答案。

示例

输入样例

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

输出样例

1
0
2
4

示例解释

初始状态：
$OOOOOOO$

D 3 后：
$OOXOOOO$

D 6 后：
$OOXOOXO$

D 5 后：
$OOXOXXO$

第一次 R 后：
$OOXOOXO$

第二次 R 后：
$OOXOOOO$

题目来源

$POJ$ 月刊--$2006.07.30$，$updog$