L. Red and Blue Edges
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an undirected graph of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Initially, there are no edges.

You should process $$$q$$$ queries. There are two types of queries:

  • $$$1~u~v$$$ — a red edge is added between vertices $$$u$$$ and $$$v$$$;
  • $$$2~u~v$$$ — a blue edge is added between vertices $$$u$$$ and $$$v$$$.

Note that the graph might contain multiple edges and/or self-loops.

After each query, find the maximum number of edges that can be deleted from the graph if the following conditions are satisfied:

  • The number of deleted red edges is equal to the number of deleted blue edges;
  • The graph connectivity isn't changed. In other words, for every pair of vertices ($$$u, v$$$), if there was a path between $$$u$$$ and $$$v$$$ before the deletion, there should still be a path between them after the deletion. Note the colors of the edges in the path don't matter.

Note that you don't actually delete the edges from the graph, you only calculate the maximum number of edges you can delete.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of vertices in the graph and the number of queries.

Each of the next $$$q$$$ lines contains three integers $$$t, u, v$$$ ($$$1 \le t \le 2$$$; $$$1 \le u, v \le n$$$) — the description of the query.

Output

After each query, print one integer — the maximum number of edges you can delete from the graph.

Examples
Input
4 5
1 3 3
2 4 4
1 1 2
2 1 2
1 1 2
Output
0
2
2
2
4
Input
5 9
2 2 5
1 4 1
1 5 3
2 5 1
1 1 3
2 3 2
1 4 2
2 4 4
1 3 5
Output
0
0
0
0
0
2
2
4
4