A connected component of an undirected graph is defined as a set of vertices $$$S$$$ of this graph such that:
- for every pair of vertices $$$(u, v)$$$ in $$$S$$$, there exists a path between vertices $$$u$$$ and $$$v$$$;
- there is no vertex outside $$$S$$$ that has a path to a vertex within $$$S$$$.
For example, the graph in the picture below has three components: $$$\{1, 3, 7, 8\}$$$, $$$\{2\}$$$, $$$\{4, 5, 6\}$$$.
We say that graph $$$A$$$ includes graph $$$B$$$ if every component of graph $$$B$$$ is a subset of some component of graph $$$A$$$.
You are given two graphs, $$$A$$$ and $$$B$$$, both consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Initially, there are no edges in the graphs. You must process queries of two types:
- add an edge to one of the graphs;
- remove an edge from one of the graphs.
After each query, you have to calculate the minimum number of edges that have to be added to $$$A$$$ so that $$$A$$$ includes $$$B$$$, and print it. Note that you don't actually add these edges, you just calculate their number.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 4 \cdot 10^5$$$; $$$1 \le q \le 4 \cdot 10^5$$$) — the number of vertices and queries, respectively.
Next, there are $$$q$$$ lines, where the $$$i$$$-th line describes the $$$i$$$-th query. The description of the query begins with the character $$$c_i$$$ (either A or B) — the graph to which the query should be applied. Then, two integers $$$x_i$$$ and $$$y_i$$$ follow ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$). If there is an edge $$$(x_i, y_i)$$$ in the corresponding graph, it should be removed; otherwise, it should be added to that graph.
For each query, print one integer — the minimum number of edges that you have to add to the graph $$$A$$$ so that it includes $$$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
