无向图的连通分量定义为该图的一组顶点 $$$S$$$,使得:
- 对于$$$S$$$中的每对顶点$$$(u, v)$$$,顶点$$$u$$$和$$$v$$$之间存在一条路径;
- $$$S$$$ 之外的顶点没有指向 $$$S$$$ 内顶点的路径。
例如,下图中的图表有三个组成部分:$$$\{1, 3, 7, 8\}$$$、$$$\{2\}$$$、$$$\{4, 5, 6\}$$$。
我们说图表$$$A$$$ 包括 图 $$$B$$$ 如果图 $$$B$$$ 的每个组件都是图 $$$A$$$ 某个组件的子集。
给您两个图,$$$A$$$ 和 $$$B$$$,两者都包含编号从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 顶点。最初,图中没有边。您必须处理两种类型的查询:
- 向其中一个图添加一条边;
- 从其中一个图中删除一条边。
每次查询后,您必须计算必须添加到 $$$A$$$ 的最小边数,以便 $$$A$$$ 包含 $$$B$$$,并打印它。请注意,您实际上并没有添加这些边,只是计算它们的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 4 \cdot 10^5$$$; $$$1 \le q \le 4 \cdot 10^5$$$) — 分别是顶点数和查询数。
接下来是 $$$q$$$ 行,其中第 $$$i$$$ 行描述第 $$$i$$$ 查询。查询的描述以字符 $$$c_i$$$ 开头(或者 A or B) — 应应用查询的图表。然后,后面跟着两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$)。如果对应图中存在边$$$(x_i, y_i)$$$,则应将其移除;否则,应将其添加到该图中。
输出
对于每个查询,打印一个整数 - 您必须添加到图形 $$$A$$$ 中的最小边数,以便它包含 $$$B$$$。
示例
输入复制
6 9A 2 3B 1 3A 2 1A 3 2B 5 6A 6 5A 3 4A 4 2A 4 3
输出复制
0 1 0 1 2 1 1 0 1