bzoj#P3009. 集合

集合

题目描述

小H在学习“集合与图论”的时候遇到了一个问题,他思考了很久依然无法很好完成这个问题。于是他只好来求助你了。

给出 n n 个点 m m 条边的带权无向图(即每条无向边上都有一个权值),有 3 3 个集合 A A B B C C 。一开始无向图中所有点都属于 A A 集合,有如下 9 9 种操作:

  • MoveAx \rm Move A \quad x :表示将第 x x 个点从所在集合中删除,并加入至 A A 集合。
  • MoveBx \rm Move B \quad x :表示将第 x x 个点从所在集合中删除,并加入至 B B 集合。
  • MoveCx \rm Move C \quad x :表示将第 x x 个点从所在集合中删除,并加入至 C C 集合。
  • AskAA \rm Ask A A :询问两个端点都属于 A A 集合的所有边中最小的权值是多少。
  • AskAB \rm Ask A B :询问两个端点分别属于 A A 集合和 B B 集合的所有边中最小的权值是多少。
  • AskAC \rm Ask A C :询问两个端点分别属于 A A 集合和 C C 集合的所有边中最小的权值是多少。
  • AskBB \rm Ask B B :询问两个端点都属于 B B 集合的所有边中最小的权值是多少。
  • AskBC \rm Ask B C :询问两个端点分别属于 B B 集合和 C C 集合的所有边中最小的权值是多少。
  • AskCC \rm Ask C C :询问两个端点都属于 C C 集合的所有边中最小的权值是多少。 你能帮助他解决这个问题吗?

输入格式

输入的第 1 1 行有两个正整数,分别表示 n n mm

在第 2 2 行至第 m+1 m+1 行中,每行有三个正整数,分别为 u u v v w w 。表示这条无向边的两个端点分别为 u u v v ( uv) u \neq v) ,且这个边的权值为 w(w109) w(w \leq 10^9)

m+2 m+2 行有一个正整数 q q ,表示有 q q 个询问。

m+3 m+3 行至第 m+q+2 m+q+2 行中,每行的输入方式为题目描述里9种操作中的一种。

输出格式

对于所有的 Ask \rm 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

数据规模与约定

对于 100%100\% 的数据,n1×105 n \leq 1\times 10^5 m5×105 m \leq 5\times 10^5 q1×105 q \leq 1\times 10^5 。且无向图上任意两个点之间至多能选出 3 3 条不相交的路径。