UOJ Logo Universal Online Judge

UOJ

#14. 【UER #1】DZY Loves Graph

统计

DZY开始有 $n$ 个点,现在他对这 $n$ 个点进行了 $m$ 次操作,对于第 $i$ 个操作(从 $1$ 开始编号)有可能的三种情况:

  1. Add a b: 表示在 $a$ 与 $b$ 之间连了一条长度为 $i$ 的边(注意,$i$是操作编号)。保证 $1 \leq a, b \leq n$。
  2. Delete k: 表示删除了当前图中边权最大的k条边。保证 $k$ 一定不会比当前图中边的条数多。
  3. Return: 表示撤销第 $i-1$ 次操作。保证第 $1$ 次操作不是 Return 且第 $i-1$ 次不是 Return 操作。

请你在每次操作后告诉DZY当前图的最小生成树边权和。如果最小生成树不存在则输出 $0$。

输入格式

第一行两个正整数 $n,m$。表示有 $n$ 个点 $m$ 个操作。 接下来 $m$ 行每行描述一个操作。

输出格式

对于每一个操作输出一行一个整数表示当前最小生成树边权和。

样例一

input

2 2
Add 1 2
Return

output

1
0

样例二

input

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

output

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}$

下载

样例数据下载