Description

While studying “Sets and Graph Theory,” Xiao H encountered a problem that he could not solve well after thinking for a long time. He asks for your help. You are given a weighted undirected graph with $n$ vertices and $m$ edges (i.e., each undirected edge has a weight). There are three sets A, B, and C. Initially, all vertices in the undirected graph belong to set A. There are nine operations as follows:

MoveA x: Remove vertex $x$ from its current set and add it to set A. MoveB x: Remove vertex $x$ from its current set and add it to set B. MoveC x: Remove vertex $x$ from its current set and add it to set C. AskAA: Query the minimum weight among all edges whose two endpoints both belong to set A. AskAB: Query the minimum weight among all edges whose two endpoints belong to sets A and B, respectively. AskAC: Query the minimum weight among all edges whose two endpoints belong to sets A and C, respectively. AskBB: Query the minimum weight among all edges whose two endpoints both belong to set B. AskBC: Query the minimum weight among all edges whose two endpoints belong to sets B and C, respectively. AskCC: Query the minimum weight among all edges whose two endpoints both belong to set C.

Can you help him solve this problem?

Input Format

• Line 1 contains two positive integers, denoting $n$ and $m$.
• Lines 2 to $m+1$: each line contains three positive integers $u$, $v$, $w$, indicating an undirected edge between $u$ and $v$ ($u \ne v$) with weight $w$ ($w \le 10^9$).
• Line $m+2$ contains a positive integer $q$, the number of operations.
• Lines $m+3$ to $m+q+2$: each line is one of the nine operations described above.

Output Format

For every Ask operation, output the minimum weight. If it does not exist, output "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

Hint

Constraints

• For 20% of the testdata, $n \le 50$, $m \le 2500$, $q \le 2500$.
• For an additional 30% of the testdata, $n \le 100$, $m \le 10000$, $q \le 20000$.
• For the remaining 50% of the testdata, $n \le 100000$, $m \le 500000$, $q \le 100000$, and in the undirected graph, between any two vertices, there exist at most 3 pairwise disjoint paths.

Translated by ChatGPT 5