| Codeforces Round 736 (Div. 1) |
|---|
| Закончено |
Есть $$$n$$$ дворян, пронумерованных от $$$1$$$ до $$$n$$$. Дворянин $$$i$$$ обладает могуществом $$$i$$$. Дворяне «дружат» между собой — всего есть $$$m$$$ пар дружных дворян. Дружба между дворянами $$$a$$$ и $$$b$$$ всегда взаимная.
Дворянин считается уязвимым, если выполнены оба следующих условия.
- у этого дворянина есть хотя бы один друг, и
- все друзья этого дворянина обладают могуществом, превосходящим могущество этого дворянина.
Вам нужно будет обрабатывать следующие три типа запросов.
- Добавить дружбу между $$$u$$$ и $$$v$$$.
- Удалить дружбу между $$$u$$$ и $$$v$$$.
- Посчитать ответ на следующий процесс.
Процесс: все уязвимые дворяне одновременно умирают, и все их дружбы заканчиваются. После этого, возможно, некоторые другие дворяне становятся уязвимыми. Процесс повторяется до тех пор, пока есть уязвимые дворяне. Можно доказать, что процесс завершится за конечное число шагов. После завершения процесса вам необходимо посчитать количество оставшихся дворян.
Заметьте, что результаты процессов не влияют на дальнейшие и предыдущие запросы, то есть все дворяне живы в начале каждого процесса!
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$) — количество дворян и количество изначальных пар друзей соответственно.
Следующие $$$m$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), описывающие дружбу между дворянами. Никакая пара друзей не повторяется дважды.
Следующая строка содержит целое число $$$q$$$ ($$$1 \le q \le 2\cdot {10}^{5}$$$) — количество запросов.
Следующие $$$q$$$ строк содержат сами запросы по одному в строке. Каждый запрос имеет один из следующих видов:
- $$$1$$$ $$$u$$$ $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$) — добавить дружбу между $$$u$$$ и $$$v$$$. Гарантируется, что $$$u$$$ и $$$v$$$ не друзья в этот момент.
- $$$2$$$ $$$u$$$ $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$) — удалить дружбу между $$$u$$$ и $$$v$$$. Гарантируется, что $$$u$$$ и $$$v$$$ дружат в этот момент.
- $$$3$$$ — вывести ответ на процесс, описанный в условии.
На каждый запрос $$$3$$$-го типа выведите целое число, по одному на строку. Гарантируется, что будет хотя бы один запрос типа $$$3$$$.
4 3 2 1 1 3 3 4 4 3 1 2 3 2 3 1 3
2 1
4 3 2 3 3 4 4 1 1 3
1
Ситуация в первом запросе типа 3 изображена на рисунке ниже.
В первом раунде процесса дворянин $$$1$$$ слабее, чем все его друзья ($$$2$$$ и $$$3$$$), и поэтому он умирает. Никакой другой дворянин в раунде 1 не является уязвимым. В раунде 2 дворянин $$$3$$$ слабее своего единственного друга, дворянина $$$4$$$, и поэтому он умирает. На этом этапе процесс завершается, ответ равен $$$2$$$.
Во втором запросе типа 3 единственным выжившим является дворянин $$$4$$$.
Второй пример состоит только из одного запроса типа $$$3$$$. В первом раунде умирают два дворянина, во втором раунде умирает один дворянин. Итоговый ответ равен $$$1$$$, поскольку только один дворянин выжил.
