Connect and Disconnect

Чи знаєте Ви що-небудь про DFS, Depth First Search, пошук у глибину?

Наприклад, використовуючи цей метод, можна перевірити зв'язність графа за час O(E). Можна навіть за той же самий час порахувати кількість компонент зв'язності графа.

Чи знаєте Ви що-небудь про DSU, Disjoint Set Union, систему множин, що не перетинаються? Використовуючи цю структуру даних, Ви можете опрацьовувати запити виду "Додати ребро у граф" і "Порахувати кількість компонент зв'язності графа" швидко. Тобто обидва запити за O(log N).

А чи знаєте Ви що-небудь про Dynamic Connectivity Problem? У цій задачі, вам потрібно вміти швидко опрацьовувати 3 типи запитів:

1. Додати ребро в граф.

2. Видалити ребро з графа.

3. Порахувати кількість компонент зв'язності графа.

Вхідні дані

На початку граф пустий.

Перший рядок вхідного файлу містить 2 числа — N і K — кількість вершин і кількість запитів (1 ≤ N ≤ 300000, 0 ≤ K ≤ 300000).

Наступні K містять запити, по одному у рядку. Є 3 типи запитів:

1. + u v: додати ребро між вершинами u і v. Гарантується, що у момент отримання запиту такого ребра у графі немає.

2. - u v: видалити ребро між вершинами u і v. Гарантується, що у момент отримання запиту таке ребро у графі єь.

3. ?: порахувати кількість компонент зв'язності у графі на поточний момент.

Вершини нумеруються від 1 до N. Немає запитів з u = v. Граф неорієнтовний.

Вихідні дані

Для кожного запиту виду '?' виведіть кількість компонент зв'язності графа у момент часу запиту у окремому рядку.

Приклади