bzoj#P3009. 集合
集合
题目描述
小H在学习“集合与图论”的时候遇到了一个问题,他思考了很久依然无法很好完成这个问题。于是他只好来求助你了。
给出 个点 条边的带权无向图(即每条无向边上都有一个权值),有 个集合 、、。一开始无向图中所有点都属于 集合,有如下 种操作:
- :表示将第 个点从所在集合中删除,并加入至 集合。
- :表示将第 个点从所在集合中删除,并加入至 集合。
- :表示将第 个点从所在集合中删除,并加入至 集合。
- :询问两个端点都属于 集合的所有边中最小的权值是多少。
- :询问两个端点分别属于 集合和 集合的所有边中最小的权值是多少。
- :询问两个端点分别属于 集合和 集合的所有边中最小的权值是多少。
- :询问两个端点都属于 集合的所有边中最小的权值是多少。
- :询问两个端点分别属于 集合和 集合的所有边中最小的权值是多少。
- :询问两个端点都属于 集合的所有边中最小的权值是多少。 你能帮助他解决这个问题吗?
输入格式
输入的第 行有两个正整数,分别表示 和 。
在第 行至第 行中,每行有三个正整数,分别为 、、。表示这条无向边的两个端点分别为 和 ( ,且这个边的权值为 。
第 行有一个正整数 ,表示有 个询问。
第 行至第 行中,每行的输入方式为题目描述里9种操作中的一种。
输出格式
对于所有的 操作输出最小的权值,如果不存在则输出No Found!
。
样例输入
4 3
1 2 1
2 3 2
3 1 3
5
AskAA
AskAB
MoveB 2
AskAA
AskAB
样例输出
1
No Found!
3
1
数据规模与约定
对于 的数据,,,。且无向图上任意两个点之间至多能选出 条不相交的路径。