集合

时间限制:10s      空间限制:128MB

题目描述

   小H在学习“集合与图论”的时候遇到了一个问题,他思考了很久依然无法很好完成这个问题。于是他只好来求助你了,给出n个点m条边的带权无向图(即每条无向边上都有一个权值),有3个集合A、B、C。一开始无向图中所有点都属于A集合,有如下9种操作:
MoveA x:表示将第x个点从所在集合中删除,并加入至A集合。
MoveB x:表示将第x个点从所在集合中删除,并加入至B集合。
MoveC x:表示将第x个点从所在集合中删除,并加入至C集合。
AskAA:询问两个端点都属于A集合的所有边中最小的权值是多少。
AskAB:询问两个端点分别属于A集合和B集合的所有边中最小的权值是多少。
AskAC:询问两个端点分别属于A集合和C集合的所有边中最小的权值是多少。
AskBB:询问两个端点都属于B集合的所有边中最小的权值是多少。
AskBC:询问两个端点分别属于B集合和C集合的所有边中最小的权值是多少。
AskCC:询问两个端点都属于C集合的所有边中最小的权值是多少。
   你能帮助他解决这个问题吗?


输入格式

 
   输入的第1行有两个正整数,分别表示n和m。
   在第2行至第m+1行中,每行有三个正整数,分别为u、v、w。表示这条无向边的两个端点分别为u和v(u != v),且这个边的权值为w(w<=10^9)。
   第m+2行有一个正整数q,表示有q个询问。
   在第m+3行至第m+q+2行中,每行的输入方式为题目描述里9种操作中的一种。


输出格式

 
  对于所有的Ask操作输出最小的权值,如果不存在则输出“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

提示

n<=100000,m<=500000,q<=100000。且无向图上任意两个点之间至多能选出3条不相交的路径。


题目来源

没有写明来源

Menuappsclose