Компонентой связности неориентированного графа назовем такое множество вершин этого графа $$$S$$$, что:
- для каждой пары вершин $$$(u, v)$$$ из множества $$$S$$$ существует путь между вершинами $$$u$$$ и $$$v$$$;
- не существует ни одной вершины вне $$$S$$$, из которой есть путь в вершину из $$$S$$$.
Например, у графа на картинке ниже три компоненты связности: $$$\{1, 3, 7, 8\}$$$, $$$\{2\}$$$, $$$\{4, 5, 6\}$$$.
Скажем, что граф $$$A$$$ включает граф $$$B$$$, если каждая компонента связности графа $$$B$$$ является подмножеством какой-то компоненты связности графа $$$A$$$.
Вам даны два графа, $$$A$$$ и $$$B$$$, оба из которых состоят из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$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, либо 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
