Cactus Graph Operations

You are given an undirected graph with n nodes numbered from \(1\) to \(n\). Each node \(i\) has an initial weight \(w_i\). Initially, there are no edges in the graph. Then, you are given \(m\) operations to perform on the graph. An operation is only legal if, after applying it, every connected component of the graph is a cactus and there is no self‐loop. (A cactus is a connected graph in which every edge belongs to at most one simple cycle.) If an operation is illegal, ignore it.

The operations are as follows:

1. Add an edge between nodes \(v\) and \(u\) with weight \(w\). (Operation: 1 v u w)
2. Remove an edge between nodes \(v\) and \(u\) with weight \(w\). (Operation: 2 v u w)
3. Add \(d\) to the weight of each node on the unique shortest path from \(v\) to \(u\). If there is no path or the shortest path is not unique, do nothing. (Operation: 3 v u d)
4. Add \(d\) to the weight of every node in the sub-cactus of \(u\) with root \(v\). The sub-cactus of \(u\) with root \(v\) is defined as the connected component that contains \(u\) after removing all edges on every simple path from \(v\) to \(u\). If \(v\) and \(u\) are not connected, do nothing. (Operation: 4 v u d)
5. Query the shortest path from \(v\) to \(u\). If there is no path, print "-1 -1". If the shortest path is not unique, print "-2 -2"; otherwise, let \(\min\) be the minimum node weight and \(\sigma\) be the sum of node weights along that unique shortest path, and output them separated by a space. (Operation: 5 v u)
6. Query the sub-cactus of \(u\) with root \(v\). If \(v\) and \(u\) are not connected, print "-1 -1"; otherwise, after removing all edges on every simple path from \(v\) to \(u\), let \(\min\) and \(\sigma\) be the minimum node weight and the sum of node weights in the connected component containing \(u\), and output them separated by a space. (Operation: 6 v u)

Input Format:
The first line contains two integers \(n\) and \(m\), separated by a space.
The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) representing the initial weights of the nodes.
Each of the following \(m\) lines describes an operation in one of the six forms described above.

Output Format:
For each query operation (types 5 and 6), output the answer on a new line. Each answer consists of two space-separated integers as described.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\). The next line contains \(n\) integers representing the initial weights of the \(n\) nodes. Each of the subsequent \(m\) lines contains an operation in one of the six formats.

outputFormat

For each operation of type 5 and 6 (queries), output a line containing two space-separated integers as specified. For type 5, output \(\min\) and \(\sigma\) for the unique shortest path (or -1 -1 if unreachable, -2 -2 if multiple shortest paths exist). For type 6, output the minimum node weight and the sum in the sub-cactus of \(u\) with root \(v\) (or -1 -1 if \(v\) and \(u\) are not connected).

sample

4 10
1 2 3 4
1 1 2 5
1 2 3 6
1 3 1 7
5 1 3
3 1 3 10
5 1 3
6 1 3
2 3 1 7
5 1 3
6 1 3

1 4
11 24
13 13
2 26
13 13