bowang0911/leetcode huggingface dataset:
Maximum Number of Coins You Can Get

There are `3n` piles of coins of varying size, you and your friends will take piles of coins as follows:

*   In each step, you will choose **any** `3` piles of coins (not necessarily consecutive).
*   Of your choice, Alice will pick the pile with the maximum number of coins.
*   You will pick the next pile with the maximum number of coins.
*   Your friend Bob will pick the last pile.
*   Repeat until there are no more piles of coins.

Given an array of integers `piles` where `piles[i]` is the number of coins in the `ith` pile.

Return the maximum number of coins that you can have.

**Example 1:**

**Input:** piles = \[2,4,1,2,7,8\]
**Output:** 9
**Explanation:** Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with **7** coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with **2** coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, **2**, 8), (2, **4**, 7) you only get 2 + 4 = 6 coins which is not optimal.

**Example 2:**

**Input:** piles = \[2,4,5\]
**Output:** 4

**Example 3:**

**Input:** piles = \[9,8,7,6,5,1,2,3,4\]
**Output:** 18

**Constraints:**

*   `3 <= piles.length <= 105`
*   `piles.length % 3 == 0`
*   `1 <= piles[i] <= 104`
Find Latest Group of Size M

Given an array `arr` that represents a permutation of numbers from `1` to `n`.

You have a binary string of size `n` that initially has all its bits set to zero. At each step `i` (assuming both the binary string and `arr` are 1-indexed) from `1` to `n`, the bit at position `arr[i]` is set to `1`.

You are also given an integer `m`. Find the latest step at which there exists a group of ones of length `m`. A group of ones is a contiguous substring of `1`'s such that it cannot be extended in either direction.

Return _the latest step at which there exists a group of ones of length **exactly**_ `m`. _If no such group exists, return_ `-1`.

**Example 1:**

**Input:** arr = \[3,5,1,2,4\], m = 1
**Output:** 4
**Explanation:** 
Step 1:  "00100 ", groups: \[ "1 "\]
Step 2:  "00101 ", groups: \[ "1 ",  "1 "\]
Step 3:  "10101 ", groups: \[ "1 ",  "1 ",  "1 "\]
Step 4:  "11101 ", groups: \[ "111 ",  "1 "\]
Step 5:  "11111 ", groups: \[ "11111 "\]
The latest step at which there exists a group of size 1 is step 4.

**Example 2:**

**Input:** arr = \[3,1,5,4,2\], m = 2
**Output:** -1
**Explanation:** 
Step 1:  "00100 ", groups: \[ "1 "\]
Step 2:  "10100 ", groups: \[ "1 ",  "1 "\]
Step 3:  "10101 ", groups: \[ "1 ",  "1 ",  "1 "\]
Step 4:  "10111 ", groups: \[ "1 ",  "111 "\]
Step 5:  "11111 ", groups: \[ "11111 "\]
No group of size 2 exists during any step.

**Constraints:**

*   `n == arr.length`
*   `1 <= m <= n <= 105`
*   `1 <= arr[i] <= n`
*   All integers in `arr` are **distinct**.
Stone Game V

There are several stones **arranged in a row**, and each stone has an associated value which is an integer given in the array `stoneValue`.

In each round of the game, Alice divides the row into **two non-empty rows** (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only **one stone remaining**. Alice's is initially **zero**.

Return _the maximum score that Alice can obtain_.

**Example 1:**

**Input:** stoneValue = \[6,2,3,4,5,5\]
**Output:** 18
**Explanation:** In the first round, Alice divides the row to \[6,2,3\], \[4,5,5\]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to \[6\], \[2,3\]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is \[2\], \[3\]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.

**Example 2:**

**Input:** stoneValue = \[7,7,7,7,7,7,7\]
**Output:** 28

**Example 3:**

**Input:** stoneValue = \[4\]
**Output:** 0

**Constraints:**

*   `1 <= stoneValue.length <= 500`
*   `1 <= stoneValue[i] <= 106`
Put Boxes Into the Warehouse I

You are given two arrays of positive integers, `boxes` and `warehouse`, representing the heights of some boxes of unit width and the heights of `n` rooms in a warehouse respectively. The warehouse's rooms are labelled from `0` to `n - 1` from left to right where `warehouse[i]` (0-indexed) is the height of the `ith` room.

Boxes are put into the warehouse by the following rules:

*   Boxes cannot be stacked.
*   You can rearrange the insertion order of the boxes.
*   Boxes can only be pushed into the warehouse from left to right only.
*   If the height of some room in the warehouse is less than the height of a box, then that box and all other boxes behind it will be stopped before that room.

Return _the maximum number of boxes you can put into the warehouse._

**Example 1:**

**Input:** boxes = \[4,3,4,1\], warehouse = \[5,3,3,4,1\]
**Output:** 3
**Explanation:** 
 
We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0.
There is no way we can fit all 4 boxes in the warehouse.

**Example 2:**

**Input:** boxes = \[1,2,2,3,4\], warehouse = \[3,4,1,2\]
**Output:** 3
**Explanation:** 
 
Notice that it's not possible to put the box of height 4 into the warehouse since it cannot pass the first room of height 3.
Also, for the last two rooms, 2 and 3, only boxes of height 1 can fit.
We can fit 3 boxes maximum as shown above. The yellow box can also be put in room 2 instead.
Swapping the orange and green boxes is also valid, or swapping one of them with the red box.

**Example 3:**

**Input:** boxes = \[1,2,3\], warehouse = \[1,2,3,4\]
**Output:** 1
**Explanation:** Since the first room in the warehouse is of height 1, we can only put boxes of height 1.

**Constraints:**

*   `n == warehouse.length`
*   `1 <= boxes.length, warehouse.length <= 105`
*   `1 <= boxes[i], warehouse[i] <= 109`
Detect Pattern of Length M Repeated K or More Times

Given an array of positive integers `arr`, find a pattern of length `m` that is repeated `k` or more times.

A **pattern** is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times **consecutively** without overlapping. A pattern is defined by its length and the number of repetitions.

Return `true` _if there exists a pattern of length_ `m` _that is repeated_ `k` _or more times, otherwise return_ `false`.

**Example 1:**

**Input:** arr = \[1,2,4,4,4,4\], m = 1, k = 3
**Output:** true
**Explanation:** The pattern **(4)** of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

**Example 2:**

**Input:** arr = \[1,2,1,2,1,1,1,3\], m = 2, k = 2
**Output:** true
**Explanation:** The pattern **(1,2)** of length 2 is repeated 2 consecutive times. Another valid pattern **(2,1) is** also repeated 2 times.

**Example 3:**

**Input:** arr = \[1,2,1,2,1,3\], m = 2, k = 3
**Output:** false
**Explanation:** The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

**Constraints:**

*   `2 <= arr.length <= 100`
*   `1 <= arr[i] <= 100`
*   `1 <= m <= 100`
*   `2 <= k <= 100`
Maximum Length of Subarray With Positive Product

Given an array of integers `nums`, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return _the maximum length of a subarray with positive product_.

**Example 1:**

**Input:** nums = \[1,-2,-3,4\]
**Output:** 4
**Explanation:** The array nums already has a positive product of 24.

**Example 2:**

**Input:** nums = \[0,1,-2,-3,-4\]
**Output:** 3
**Explanation:** The longest subarray with positive product is \[1,-2,-3\] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

**Example 3:**

**Input:** nums = \[-1,-2,-3,0,1\]
**Output:** 2
**Explanation:** The longest subarray with positive product is \[-1,-2\] or \[-2,-3\].

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
Minimum Number of Days to Disconnect Island

You are given an `m x n` binary grid `grid` where `1` represents land and `0` represents water. An **island** is a maximal **4-directionally** (horizontal or vertical) connected group of `1`'s.

The grid is said to be **connected** if we have **exactly one island**, otherwise is said **disconnected**.

In one day, we are allowed to change **any** single land cell `(1)` into a water cell `(0)`.

Return _the minimum number of days to disconnect the grid_.

**Example 1:**

**Input:** grid = \[\[0,1,1,0\],\[0,1,1,0\],\[0,0,0,0\]\]

**Output:** 2
**Explanation:** We need at least 2 days to get a disconnected grid.
Change land grid\[1\]\[1\] and grid\[0\]\[2\] to water and get 2 disconnected island.

**Example 2:**

**Input:** grid = \[\[1,1\]\]
**Output:** 2
**Explanation:** Grid of full water is also disconnected (\[\[1,1\]\] -> \[\[0,0\]\]), 0 islands.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 30`
*   `grid[i][j]` is either `0` or `1`.
Number of Ways to Reorder Array to Get Same BST

Given an array `nums` that represents a permutation of integers from `1` to `n`. We are going to construct a binary search tree (BST) by inserting the elements of `nums` in order into an initially empty BST. Find the number of different ways to reorder `nums` so that the constructed BST is identical to that formed from the original array `nums`.

*   For example, given `nums = [2,1,3]`, we will have 2 as the root, 1 as a left child, and 3 as a right child. The array `[2,3,1]` also yields the same BST but `[3,2,1]` yields a different BST.

Return _the number of ways to reorder_ `nums` _such that the BST formed is identical to the original BST formed from_ `nums`.

Since the answer may be very large, **return it modulo** `109 + 7`.

**Example 1:**

**Input:** nums = \[2,1,3\]
**Output:** 1
**Explanation:** We can reorder nums to be \[2,3,1\] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

**Example 2:**

**Input:** nums = \[3,4,5,1,2\]
**Output:** 5
**Explanation:** The following 5 arrays will yield the same BST: 
\[3,1,2,4,5\]
\[3,1,4,2,5\]
\[3,1,4,5,2\]
\[3,4,1,2,5\]
\[3,4,1,5,2\]

**Example 3:**

**Input:** nums = \[1,2,3\]
**Output:** 0
**Explanation:** There are no other orderings of nums that will yield the same BST.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= nums.length`
*   All integers in `nums` are **distinct**.
Dot Product of Two Sparse Vectors

Given two sparse vectors, compute their dot product.

Implement class `SparseVector`:

*   `SparseVector(nums)` Initializes the object with the vector `nums`
*   `dotProduct(vec)` Compute the dot product between the instance of _SparseVector_ and `vec`

A **sparse vector** is a vector that has mostly zero values, you should store the sparse vector **efficiently** and compute the dot product between two _SparseVector_.

**Follow up:** What if only one of the vectors is sparse?

**Example 1:**

**Input:** nums1 = \[1,0,0,2,3\], nums2 = \[0,3,0,4,0\]
**Output:** 8
**Explanation:** v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1\*0 + 0\*3 + 0\*0 + 2\*4 + 3\*0 = 8

**Example 2:**

**Input:** nums1 = \[0,1,0,0,0\], nums2 = \[0,0,0,0,2\]
**Output:** 0
**Explanation:** v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0\*0 + 1\*0 + 0\*0 + 0\*0 + 0\*2 = 0

**Example 3:**

**Input:** nums1 = \[0,1,0,0,2,0,0\], nums2 = \[1,0,0,0,3,0,4\]
**Output:** 6

**Constraints:**

*   `n == nums1.length == nums2.length`
*   `1 <= n <= 10^5`
*   `0 <= nums1[i], nums2[i] <= 100`
Matrix Diagonal Sum

Given a square matrix `mat`, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

**Example 1:**

**Input:** mat = \[\[**1**,2,**3**\],
              \[4,**5**,6\],
              \[**7**,8,**9**\]\]
**Output:** 25
**Explanation:** Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat\[1\]\[1\] = 5 is counted only once.

**Example 2:**

**Input:** mat = \[\[**1**,1,1,**1**\],
              \[1,**1**,**1**,1\],
              \[1,**1**,**1**,1\],
              \[**1**,1,1,**1**\]\]
**Output:** 8

**Example 3:**

**Input:** mat = \[\[**5**\]\]
**Output:** 5

**Constraints:**

*   `n == mat.length == mat[i].length`
*   `1 <= n <= 100`
*   `1 <= mat[i][j] <= 100`
Number of Ways to Split a String

Given a binary string `s`, you can split `s` into 3 **non-empty** strings `s1`, `s2`, and `s3` where `s1 + s2 + s3 = s`.

Return the number of ways `s` can be split such that the number of ones is the same in `s1`, `s2`, and `s3`. Since the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** s =  "10101 "
**Output:** 4
**Explanation:** There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
 "1|010|1 "
 "1|01|01 "
 "10|10|1 "
 "10|1|01 "

**Example 2:**

**Input:** s =  "1001 "
**Output:** 0

**Example 3:**

**Input:** s =  "0000 "
**Output:** 3
**Explanation:** There are three ways to split s in 3 parts.
 "0|0|00 "
 "0|00|0 "
 "00|0|0 "

**Constraints:**

*   `3 <= s.length <= 105`
*   `s[i]` is either `'0'` or `'1'`.
Shortest Subarray to be Removed to Make Array Sorted

Given an integer array `arr`, remove a subarray (can be empty) from `arr` such that the remaining elements in `arr` are **non-decreasing**.

Return _the length of the shortest subarray to remove_.

A **subarray** is a contiguous subsequence of the array.

**Example 1:**

**Input:** arr = \[1,2,3,10,4,2,3,5\]
**Output:** 3
**Explanation:** The shortest subarray we can remove is \[10,4,2\] of length 3. The remaining elements after that will be \[1,2,3,3,5\] which are sorted.
Another correct solution is to remove the subarray \[3,10,4\].

**Example 2:**

**Input:** arr = \[5,4,3,2,1\]
**Output:** 4
**Explanation:** Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either \[5,4,3,2\] or \[4,3,2,1\].

**Example 3:**

**Input:** arr = \[1,2,3\]
**Output:** 0
**Explanation:** The array is already non-decreasing. We do not need to remove any elements.

**Constraints:**

*   `1 <= arr.length <= 105`
*   `0 <= arr[i] <= 109`
Count All Possible Routes

You are given an array of **distinct** positive integers locations where `locations[i]` represents the position of city `i`. You are also given integers `start`, `finish` and `fuel` representing the starting city, ending city, and the initial amount of fuel you have, respectively.

At each step, if you are at city `i`, you can pick any city `j` such that `j != i` and `0 <= j < locations.length` and move to city `j`. Moving from city `i` to city `j` reduces the amount of fuel you have by `|locations[i] - locations[j]|`. Please notice that `|x|` denotes the absolute value of `x`.

Notice that `fuel` **cannot** become negative at any point in time, and that you are **allowed** to visit any city more than once (including `start` and `finish`).

Return _the count of all possible routes from_ `start` _to_ `finish`. Since the answer may be too large, return it modulo `109 + 7`.

**Example 1:**

**Input:** locations = \[2,3,6,8,4\], start = 1, finish = 3, fuel = 5
**Output:** 4
**Explanation:** The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

**Example 2:**

**Input:** locations = \[4,3,1\], start = 1, finish = 0, fuel = 6
**Output:** 5
**Explanation:** The following are all possible routes:
1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

**Example 3:**

**Input:** locations = \[5,2,1\], start = 0, finish = 2, fuel = 3
**Output:** 0
**Explanation:** It is impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

**Constraints:**

*   `2 <= locations.length <= 100`
*   `1 <= locations[i] <= 109`
*   All integers in `locations` are **distinct**.
*   `0 <= start, finish < locations.length`
*   `1 <= fuel <= 200`
Replace All ?'s to Avoid Consecutive Repeating Characters

Given a string `s` containing only lowercase English letters and the `'?'` character, convert **all** the `'?'` characters into lowercase letters such that the final string does not contain any **consecutive repeating** characters. You **cannot** modify the non `'?'` characters.

It is **guaranteed** that there are no consecutive repeating characters in the given string **except** for `'?'`.

Return _the final string after all the conversions (possibly zero) have been made_. If there is more than one solution, return **any of them**. It can be shown that an answer is always possible with the given constraints.

**Example 1:**

**Input:** s =  "?zs "
**Output:**  "azs "
**Explanation:** There are 25 solutions for this problem. From  "azs " to  "yzs ", all are valid. Only  "z " is an invalid modification as the string will consist of consecutive repeating characters in  "zzs ".

**Example 2:**

**Input:** s =  "ubv?w "
**Output:**  "ubvaw "
**Explanation:** There are 24 solutions for this problem. Only  "v " and  "w " are invalid modifications as the strings will consist of consecutive repeating characters in  "ubvvw " and  "ubvww ".

**Constraints:**

*   `1 <= s.length <= 100`
*   `s` consist of lowercase English letters and `'?'`.
Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Given two arrays of integers `nums1` and `nums2`, return the number of triplets formed (type 1 and type 2) under the following rules:

*   Type 1: Triplet (i, j, k) if `nums1[i]2 == nums2[j] * nums2[k]` where `0 <= i < nums1.length` and `0 <= j < k < nums2.length`.
*   Type 2: Triplet (i, j, k) if `nums2[i]2 == nums1[j] * nums1[k]` where `0 <= i < nums2.length` and `0 <= j < k < nums1.length`.

**Example 1:**

**Input:** nums1 = \[7,4\], nums2 = \[5,2,8,9\]
**Output:** 1
**Explanation:** Type 1: (1, 1, 2), nums1\[1\]2 = nums2\[1\] \* nums2\[2\]. (42 = 2 \* 8). 

**Example 2:**

**Input:** nums1 = \[1,1\], nums2 = \[1,1,1\]
**Output:** 9
**Explanation:** All Triplets are valid, because 12 = 1 \* 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1\[i\]2 = nums2\[j\] \* nums2\[k\].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2\[i\]2 = nums1\[j\] \* nums1\[k\].

**Example 3:**

**Input:** nums1 = \[7,7,8,3\], nums2 = \[1,2,9,7\]
**Output:** 2
**Explanation:** There are 2 valid triplets.
Type 1: (3,0,2).  nums1\[3\]2 = nums2\[0\] \* nums2\[2\].
Type 2: (3,0,1).  nums2\[3\]2 = nums1\[0\] \* nums1\[1\].

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 1000`
*   `1 <= nums1[i], nums2[i] <= 105`
Minimum Time to Make Rope Colorful

Alice has `n` balloons arranged on a rope. You are given a **0-indexed** string `colors` where `colors[i]` is the color of the `ith` balloon.

Alice wants the rope to be **colorful**. She does not want **two consecutive balloons** to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it **colorful**. You are given a **0-indexed** integer array `neededTime` where `neededTime[i]` is the time (in seconds) that Bob needs to remove the `ith` balloon from the rope.

Return _the **minimum time** Bob needs to make the rope **colorful**_.

**Example 1:**

**Input:** colors =  "abaac ", neededTime = \[1,2,3,4,5\]
**Output:** 3
**Explanation:** In the above image, 'a' is blue, 'b' is red, and 'c' is green.
Bob can remove the blue balloon at index 2. This takes 3 seconds.
There are no longer two consecutive balloons of the same color. Total time = 3.

**Example 2:**

**Input:** colors =  "abc ", neededTime = \[1,2,3\]
**Output:** 0
**Explanation:** The rope is already colorful. Bob does not need to remove any balloons from the rope.

**Example 3:**

**Input:** colors =  "aabaa ", neededTime = \[1,2,3,4,1\]
**Output:** 2
**Explanation:** Bob will remove the ballons at indices 0 and 4. Each ballon takes 1 second to remove.
There are no longer two consecutive balloons of the same color. Total time = 1 + 1 = 2.

**Constraints:**

*   `n == colors.length == neededTime.length`
*   `1 <= n <= 105`
*   `1 <= neededTime[i] <= 104`
*   `colors` contains only lowercase English letters.
Remove Max Number of Edges to Keep Graph Fully Traversable

Alice and Bob have an undirected graph of `n` nodes and three types of edges:

*   Type 1: Can be traversed by Alice only.
*   Type 2: Can be traversed by Bob only.
*   Type 3: Can be traversed by both Alice and Bob.

Given an array `edges` where `edges[i] = [typei, ui, vi]` represents a bidirectional edge of type `typei` between nodes `ui` and `vi`, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return _the maximum number of edges you can remove, or return_ `-1` _if Alice and Bob cannot fully traverse the graph._

**Example 1:**

**Input:** n = 4, edges = \[\[3,1,2\],\[3,2,3\],\[1,1,3\],\[1,2,4\],\[1,1,2\],\[2,3,4\]\]
**Output:** 2
**Explanation:** If we remove the 2 edges \[1,1,2\] and \[1,1,3\]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

**Example 2:**

**Input:** n = 4, edges = \[\[3,1,2\],\[3,2,3\],\[1,1,4\],\[2,1,4\]\]
**Output:** 0
**Explanation:** Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

**Example 3:**

**Input:** n = 4, edges = \[\[3,2,3\],\[1,1,2\],\[2,3,4\]\]
**Output:** -1
**Explanation:** In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

**Constraints:**

*   `1 <= n <= 105`
*   `1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)`
*   `edges[i].length == 3`
*   `1 <= typei <= 3`
*   `1 <= ui < vi <= n`
*   All tuples `(typei, ui, vi)` are distinct.