Card Swipe Marathon

The school has introduced a card swiping system so that students can monitor themselves. There are \(n\) locations numbered from \(1\) to \(n\). Each location is equipped with several card machines. There are three kinds of events:

• Event 1: A runway connecting location \(A\) and location \(B\) is constructed. After construction, a direction is assigned to this runway so that it can be used in only one direction.
• Event 2: The number of card machines at location \(A\) is updated to \(B\).
• Event 3: A long run is initiated. A student starts at location \(A\) and finally reaches location \(B\). Upon arriving at any location, the student may swipe on every card machine at that location. However, each card machine can be swiped at most once over the entire run (even if the location is visited multiple times). Considering that the runway directions can be chosen arbitrarily when constructed, compute the maximum number of card swipes possible when travelling from \(A\) to \(B\) along some path.

Note: Initially, every location has 0 card machines. For any Event 3, if \(B\) is not reachable from \(A\) (i.e. \(A\) and \(B\) are not in the same connected component when treating each runway as an undirected edge), output \(-1\); otherwise, it can be proven that by properly assigning directions to the runways and planning a route (possibly by revisiting locations but counting each location's machines only once) you can collect all the card machines in the connected component. Thus, the answer is the sum of the card machine counts in that connected component.

inputFormat

The first line contains two integers \(n\) and \(q\) where \(n\) is the number of locations and \(q\) is the number of events. Then \(q\) lines follow, each containing an event in one of the following formats:

• 1 A B: A runway is constructed between locations \(A\) and \(B\).
• 2 A B: The number of card machines at location \(A\) is updated to \(B\).
• 3 A B: A long run is initiated from location \(A\) to location \(B\). Query the maximum number of card swipes possible.

All indices are 1-indexed. Initially, every location has 0 card machines.

outputFormat

For each event of type 3, output a single line containing one integer — the maximum number of card swipes obtainable if a student travels from \(A\) to \(B\) collecting the swipes from each location in the connected component (each card machine counted only once). If \(B\) is not reachable from \(A\), output \(-1\).

sample

5 8
2 1 10
2 2 5
1 1 2
3 1 2
2 3 4
1 2 3
3 1 3
3 4 5

15
19
-1