← 返回题目列表

Codeforces · 2069/F

F. 图包含

中文机器翻译题面 查看原题

无向图的连通分量定义为该图的一组顶点 $$$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 9
A 2 3
B 1 3
A 2 1
A 3 2
B 5 6
A 6 5
A 3 4
A 4 2
A 4 3

输出
复制

0
1
0
1
2
1
1
0
1