Graph Queries on Colored Paths

You are given an undirected graph \(G\) with \(n\) nodes and \(m\) edges. Each node \(i\) has an initial weight \(w_i\), and each edge has a color represented by an integer. The graph satisfies the following two conditions:

• For any node, among the edges incident to it, there are at most two edges of the same color.
• The graph does not contain any cycle formed by edges of the same color. (A same-colored cycle means a cycle whose edges all share the same color.)

You need to support the following three types of operations:

1. 0 x y: Change the weight of node \(x\) to \(y\).
2. 1 u v w: Change the color of edge \((u,v)\) to \(w\). It is guaranteed that the edge exists.
3. 2 c u v: In the subgraph formed only by edges of color \(c\), consider the unique simple path (if it exists) between nodes \(u\) and \(v\) (note that, by the restrictions, each connected component in such a subgraph is a simple path). Output the maximum weight among all the nodes on the simple path from \(u\) to \(v\). If there is no such path, output -1.

Input Format:

The first line contains three integers \(n, m, q\) representing the number of nodes, edges, and operations respectively. The second line contains \(n\) integers representing the initial node weights \(w_1, w_2, \dots, w_n\). The next \(m\) lines each contain three integers \(u, v, c\), describing an edge between nodes \(u\) and \(v\) with color \(c\). Then, \(q\) lines follow, each describing an operation in one of the three formats mentioned above.

Note: The nodes are numbered from 1 to \(n\). It is guaranteed that no operation will violate the conditions of the graph.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) (number of nodes, edges, and operations).
The second line contains \(n\) integers \(w_1, w_2, \ldots, w_n\) representing the weights of the nodes.
Each of the next \(m\) lines contains three integers \(u, v, c\) representing an edge between nodes \(u\) and \(v\) with color \(c\).
Then \(q\) lines follow, each representing an operation in one of the following formats:
0 x y — update the weight of node \(x\) to \(y\).
1 u v w — update the color of the edge connecting nodes \(u\) and \(v\) to \(w\).
2 c u v — query in the subgraph formed by edges of color \(c\), the maximum node weight along the unique simple path from \(u\) to \(v\). If there is no such path, output -1.

outputFormat

For each query operation of type 2, output a single line containing the answer. If there is no path between \(u\) and \(v\) in the subgraph, output -1.

sample

5 4 5
1 5 3 4 2
1 2 1
2 3 1
3 4 2
4 5 2
2 1 1 3
0 2 10
2 1 1 3
1 3 4 1
2 1 1 4

5
10
10