P2500 [SDOI2012] Set

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?

- 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.

For every Ask operation, output the minimum weight. If it does not exist, output "No Found!".

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