EduBrick

M. Соединение и разъединение

4000 мс · 512 МБ · всё или ничего

Граф на nn вершинах, изначально без рёбер. Обрабатывайте запросы:

  • + u v — добавить ребро (такого ребра сейчас нет);
  • - u v — удалить ребро (такое ребро сейчас есть);
  • ? — вывести количество компонент связности.

Формат ввода

В первой строке — числа nn и kk (1≤n≤3⋅1051 \le n \le 3 \cdot 10^5, 0≤k≤3⋅1050 \le k \le 3 \cdot 10^5). Далее kk запросов в описанном формате; u≠vu \ne v.

Формат вывода

На каждый запрос ? выведите количество компонент связности.

Примеры

ввод
5 11
?
+ 1 2
+ 2 3
+ 3 4
+ 4 5
+ 5 1
?
- 2 3
?
- 4 5
?
вывод
5
1
1
2
ввод
2 1
?
вывод
2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.