【UER #1】DZY Loves Graph
DZY开始有 $n$ 个点，现在他对这 $n$ 个点进行了 $m$ 次操作，对于第 $i$ 个操作（从 $1$ 开始编号）有可能的三种情况：
- Add a b： 表示在 $a$ 与 $b$ 之间连了一条长度为 $i$ 的边（注意，$i$是操作编号）。保证 $1 \leq a, b \leq n$。
- Delete k： 表示删除了当前图中边权最大的k条边。保证 $k$ 一定不会比当前图中边的条数多。
- Return： 表示撤销第 $i-1$ 次操作。保证第 $1$ 次操作不是 Return 且第 $i-1$ 次不是 Return 操作。
请你在每次操作后告诉DZY当前图的最小生成树边权和。如果最小生成树不存在则输出 $0$。
输入格式
第一行两个正整数 $n,m$。表示有 $n$ 个点 $m$ 个操作。 接下来 $m$ 行每行描述一个操作。
输出格式
对于每一个操作输出一行一个整数表示当前最小生成树边权和。
2 2
Add 1 2
Return
1
0
5 10
Add 2 1
Add 3 2
Add 4 2
Add 5 2
Add 2 3
Return
Delete 1
Add 2 3
Add 5 2
Return
0
0
0
10
10
10
0
0
15
0
样例三
见样例数据下载
限制与约定
| 测试点编号 | $n$ | $m$ | 其他 |
|---|---|---|---|
| 1 | $n \leq 10^3$ | $m \leq 10^3$ | 只有Add操作 |
| 2 | |||
| 3 | |||
| 4 | $n \leq 2 \times 10^5$ | $m \leq 2 \times 10^5$ | 只有Add操作 |
| 5 | $n \leq 3 \times 10^5$ | $m \leq 5 \times 10^5$ | |
| 6 | $n \leq 2 \times 10^5$ | $m \leq 2 \times 10^5$ | 没有Return操作 |
| 7 | $n \leq 3 \times 10^5$ | $m \leq 5 \times 10^5$ | |
| 8 | $n \leq 2 \times 10^5$ | $m \leq 2 \times 10^5$ | |
| 9 | $n \leq 3 \times 10^5$ | $m \leq 5 \times 10^5$ | |
| 10 |
时间限制：$1\texttt{s}$
空间限制：$64\texttt{MB}$