Weighted Graph Set Operations

You are given an undirected weighted graph with n nodes and m edges. Each edge has a weight. Initially, every node belongs to set A. You are also given a sequence of operations. There are two types of operations:

• Move operations:
  • MoveA x: Remove node x from its current set and add it to set A.
  • MoveB x: Remove node x from its current set and add it to set B.
  • MoveC x: Remove node x from its current set and add it to set C.
• Query operations: These ask for the minimum edge weight among all edges whose endpoints belong to the specified sets. The queries are:
  • AskAA: Both endpoints in set A.
  • AskAB: One endpoint in set A and the other in set B.
  • AskAC: One endpoint in set A and the other in set C.
  • AskBB: Both endpoints in set B.
  • AskBC: One endpoint in set B and the other in set C.
  • AskCC: Both endpoints in set C.

For any query, if no eligible edge exists, output -1.

Note: The edge condition for queries AskXY (where X and Y are sets) is interpreted as: if X equals Y then both endpoints must belong to X; if X and Y are different then one endpoint must belong to X and the other to Y.

The task is to simulate the operations sequentially and answer each query accordingly.

Mathematical formulation:

Let the graph be represented as \( G=(V, E) \) where \( V = \{1,2,\ldots,n\} \) and each edge \( e=(u,v) \) has a weight \( w_e \). Initially, for all \( u \in V, \; s(u)=A \). Then, for each operation:

• If the operation is MoveX x (where X is A, B, or C), update \( s(x)=X \).
• If the operation is AskXY, answer \( \min\{w_e: e=(u,v)\in E, \; [s(u)=X \; \text{and} \; s(v)=Y] \text{ or } [s(u)=Y \; \text{and} \; s(v)=X] \} \) with the convention that if no such edge exists, then output \(-1\).

inputFormat

The first line contains three integers n m q \( (1 \leq n, m, q \leq 10^5) \), representing the number of nodes, the number of edges, and the number of operations, respectively.

The next \( m \) lines each contain three integers u v w, describing an undirected edge between nodes u and v with weight w \( (1 \leq u,v \leq n, 1 \leq w \leq 10^9) \).

The following \( q \) lines each contain one operation, which is one of the following forms:

• MoveA x
• MoveB x
• MoveC x
• AskAA
• AskAB
• AskAC
• AskBB
• AskBC
• AskCC

It is guaranteed that the operations are valid and that x is a valid node index.

outputFormat

For each query operation, output a single line with one integer, representing the minimum weight among all eligible edges. If there is no such edge, output -1.

sample

4 4 5
1 2 3
2 3 4
3 4 2
1 4 6
AskAA
MoveB 2
AskAB
MoveC 4
AskAC

2
3
2

</p>