Connect and Disconnect#1881
Sign in

Connect and Disconnect

3 seconds
256 megabytes
Easy

Are you familiar with DFS, or Depth First Search?

Using this technique, you can check whether a graph is connected in time. You can also count the number of connected components in a graph within the same time.

Have you heard of DSU, or Disjoint Set Union? This data structure allows you to efficiently handle queries like "Add an edge to the graph" and "Count the number of connected components in the graph." Both queries can be processed in O(\log N) time.

What about the Dynamic Connectivity Problem? In this problem, you must efficiently answer types of queries:

  1. Add an edge to the graph.

  2. Remove an edge from the graph.

  3. Count the number of connected components in the graph.

Input

Initially, the graph is empty.

The first line contains numbers — and — the number of vertices and the number of queries (1 \le N \le 300\,000, 0 \le K \le 300\,000).

The next lines contain queries, one per line. There are possible types:

  1. : Add an edge between vertices and . It is guaranteed that such an edge does not exist in the graph at the time of the query.

  2. : Remove an edge between vertices and . It is guaranteed that such an edge exists in the graph at the time of the query.

  3. : Count the number of connected components in the graph at the current moment.

Vertices are numbered from to . There are no queries where u = v. The graph is undirected.

Output

For each query of type output the number of connected components in the graph at that moment on a separate line.

Examples

Example 1

Loading
Loading