Background

A school has launched a popular “Sunshine Long-Distance Run” activity. To “work healthily for the motherland for fifty years”, students leave their dorms, classrooms, and labs to join a $3000$-meter run on the playground. In no time, the playground becomes packed with people, creating an unprecedented lively scene.

Problem Description

To help students supervise themselves better, the school uses a card-swiping system. There are $n$ locations in the school, labeled by integers $1 \sim n$. Each location has several card-swiping machines.

There are three types of events:

1. Build a track connecting location $A$ and location $B$.
2. The number of card-swiping machines at location $A$ becomes $B$.
3. Perform a long-distance run. Ask: if a student starts from location $A$ and finally arrives at location $B$, what is the maximum number of times they can swipe their card. The specific rules are:
   • When the student arrives at a location, they may swipe on every machine there. But each machine can be used at most once. That is, even if they visit the same location multiple times, they cannot swipe on the same machine more than once. For safety, each track must be assigned a direction, and it can only be traveled one-way along that direction. The maximum number of swipes is defined as: after choosing directions for all tracks arbitrarily, and choosing any path from $A$ to $B$, the maximum total number of swipes possible.

Input Format

The first line contains two positive integers $n, m$.

The second line contains $n$ positive integers. The $i$-th integer is the number of card-swiping machines at location $i$.

The next $m$ lines each contain three non-negative integers $P, A, B$, describing one event. $P$ is the event type, and $A, B$ are the two parameters of the event.

Output Format

For each event with $P = 3$, output one line containing one integer: the maximum number of swipes possible when traveling from $A$ to $B$ along some path, with track directions chosen arbitrarily. If $B$ cannot be reached, output $-1$.

9 31
10 20 30 40 50 60 70 80 90
3 1 2
1 1 3
1 1 2
1 8 9
1 2 4
1 2 5
1 4 6
1 4 7
3 1 8
3 8 8
1 8 9
3 8 8
3 7 5
3 7 3
1 4 1
3 7 5
3 7 3
1 5 7
3 6 5
3 3 6
1 2 4
1 5 5
3 3 6
2 8 180
3 8 8
2 9 190
3 9 9
2 5 150
3 3 6
2 1 210
3 3 6

-1
-1
80
170
180
170
190
170
250
280
280
270
370
380
580

Hint

For all testdata, $1 \leq m \leq 5n$, $1 \leq n \leq 1.5 \times 10^5$.

It is guaranteed that initially there are no tracks between any locations.

In each line, adjacent numbers are separated by a single space.

All location indices are between $1$ and $n$. The number of card-swiping machines at each location never exceeds $10^4$. $P \in \{1, 2, 3\}$.

Translated by ChatGPT 5