Background

Template problem.

Problem Description

There are $n$ vertices, numbered from $1 \sim n$. Vertex $i$ has a weight $w_i$. Initially, there are no edges.

There are $m$ operations. An operation is considered valid if, after applying it, every connected component of this undirected graph is a cactus, and there are no self-loops. Otherwise, the operation is invalid. Invalid operations are ignored. There are six types of operations:

1. Add an edge of weight $w$ between vertices $v$ and $u$.

2. Delete an edge of weight $w$ between vertices $v$ and $u$.

3. Add $d$ to the weight of every vertex on the shortest path from vertex $v$ to vertex $u$.

4. Add $d$ to the weight of every vertex in the sub-cactus $u$, rooted at vertex $v$.

5. Query information about the shortest path from vertex $v$ to vertex $u$.

   Output two integers $min,\sigma$ separated by a space, representing the minimum vertex weight and the sum of vertex weights on the shortest path.

   If there is no path reachable, then $min=-1,\sigma =-1$.

   If the shortest path is not unique, then $min=-2,\sigma =-2$.

6. Query information about the sub-cactus $u$, rooted at vertex $v$.

   Output two integers $min,\sigma$ separated by a space, representing the minimum vertex weight and the sum of vertex weights in sub-cactus $u$.

   If $v$ and $u$ are not connected, then $min=-1,\sigma =-1$.

The definition of the sub-cactus $u$ rooted at vertex $v$ is: after deleting the edges on all simple paths between $v$ and $u$, the connected component containing $u$.

Input Format

The first line contains two positive integers $n,m$ separated by spaces, meaning there are $n$ vertices and $m$ operations in total.

The next line contains $n$ positive integers. The $i$-th positive integer is $w_i$.

The next $m$ lines each describe one operation. Each line starts with three integers: $opt_i,v_i,u_i$.

If $opt_i \in \{ 1,2,3,4 \}$, then one more integer follows; otherwise, the line ends.

Output Format

For operations $5$ and $6$, output the corresponding results.

11 23
10 5 11 7 8 14 30 3 16 20 19
1 1 2 5
1 2 3 3
1 3 4 7
1 4 5 8
1 2 6 10
1 6 7 15
1 4 7 3
1 6 8 9
1 6 8 6
1 7 9 12
1 9 11 10
1 7 10 4
1 9 10 8
5 5 11
5 2 10
6 8 7
3 8 5 100
5 1 7
6 8 7
4 11 7 1000
5 8 3
4 3 2 2333
5 1 5

-2 -2
5 73
16 85
5 263
16 185
1005 4233
1011 9907

Hint

Constraints
For $100\%$ of the testdata, $1 \leq n \leq 50000, 1 \leq m \leq 250000$.

It is guaranteed that in operations $1$ and $2$, $w$ satisfies $1 \leq w \leq 10000$, so computations involving edge weights will not exceed the range of a 32-bit signed integer.

It is guaranteed that the initial $w_i$ does not exceed $10^9$, and that the sum of all $d$ in operations $3$ and $4$ does not exceed $10^9$.

Translated by ChatGPT 5