1785: Ізольовані вершини
Перегляд у форматі PDFІснує неорієнтований граф з ~N~ вершинами, пронумерованими від 1 до ~N~, кількість ребер на початку рівна 0.
Обробіть ~Q~ запитів у порядку їх слідування. Після обробки кожного запиту виведіть кількість вершин, які не з'єднані ребром з іншими вершинами.
~I~-й запит ~q_i~ належить до одного з двох наступних типів:
-- 1 ~u~ ~v~: з'єднати вершину ~u~ і вершину ~v~ ребром. Гарантується, що коли задається цей запит, вершина ~u~ та вершина ~v~ не з'єднані ребром.
-- 2 ~v~: видаліть усі ребра, які з'єднують вершину ~v~ та інші вершини. (Сама вершина ~v~ не видаляється.)
Обмеження
- ~2 \le N \le 3 \cdot 10^5~
- ~1 \le Q \le 3 \cdot 10^5~
- Для кожного запиту першого типу ~1 \le u,v \le N~ і ~u \neq v~.
- Для кожного запиту другого типу ~1 \le v \le N~.
- Безпосередньо перед подачею запиту першого типу між вершинами ~u~ і ~v~ немає ребра.
- Усі значення у вхідних даних є цілими числами.
Формат вхідних даних
Перший рядок вхідного потоку містить цілі числа ~N, Q~.
Наступні ~Q~ рядків містять запити ~q_i~.
Формат вихідних даних
У вихідний потік вивести ~Q~ рядків. В ~i~-му рядку ~(1 \le i \le Q)~ має бути записано кількість вершин, які не з'єднані ребром з іншими вершинами.
Пояснення
Приклад вхідних 1:
Після першого запиту вершина 1 і вершина 2 з'єднані одна з одною ребром, але вершина 3 не з'єднана з іншими вершинами. Таким чином, 1 виводимо в першому рядку.
Після третього запиту всі пари різних вершин з'єднуються ребром.
Четвертий запит просить видалити всі ребра, які з'єднують вершину 1 та інші вершини, зокрема, видалити ребро між вершиною 1 і вершиною 2, а також між вершиною 1 і вершиною 3. У результаті вершина 2 і вершина 3 з'єднані одна з одною, тоді як вершина 1 не з'єднана ребром з іншими вершинами. Таким чином, виводимо 0 і 1 в третьому і четвертому рядках відповідно.
Приклад вхідних даних
3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2
Приклад вихідних даних
1
0
0
1
0
3
1
Приклад вхідних даних
2 1
2 1
Приклад вихідних даних
2
Коментарі
Додайте часу для Python, будь ласка, реалізації одного алгоритму на Python 3.7 та С++ 17 набирають 26 та 100 балів відповідно
Додав