Interactive Graph Pairing

This is an interactive problem. You are given N points numbered from 1 to N and need to process Q queries on an initially empty graph.

There are three types of queries:

• a u v p: Add an undirected edge between node u and node v with length p.
• r: Remove the longest undirected edge currently in the graph. (If there are multiple edges with equal maximum length, remove any one of them.)
• d: Consider the connected components of the current graph. Pair the components into pairs. If the number of components is odd, one component is paired with a dummy component of size 0. Let a connected component A have size \( |A| \). You need to determine the minimum possible value of \( \displaystyle \sum_{i} \Big| |A_i| - |B_i| \Big| \) over all possible pairings.

Note on the pairing: If the components sizes are sorted as \( s_1, s_2, \ldots, s_m \), then if \( m \) is even an optimal pairing is to pair adjacent components, giving a cost of \( \sum_{i=1}^{m/2} (s_{2i} - s_{2i-1}) \). If \( m \) is odd, you are allowed to pair one component with the dummy (adding that component's size as cost) and pair the rest optimally. For example, if \( m=3 \) and \( s_1 \le s_2 \le s_3 \), the answer is \( \min\{ s_1+(s_3-s_2),\ s_2+(s_3-s_1)\} \).

You must process the queries in the given order. For each query of type d, output the minimum possible cost computed as described above.

inputFormat

The first line contains two integers N and Q representing the number of nodes and the number of queries.

The following Q lines contain one query each. Each query is in one of the following formats:

• a u v p
• r
• d

It is guaranteed that when a removal query r is issued, there is at least one edge in the graph.

outputFormat

For each query of type d, output a single integer, the minimum possible pairing cost, in the order the queries appear.

sample

5 5
d
a 1 2 3
d
a 2 3 2
d

1
1
3