CareerCup

N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

We define the following:

There are friends_nodes friends numbered from 1 to friends_nodes.
There are friends_edges pairs of friends, where each (xi, yi) pair of friends is connected by a shared integer token described by friends_weighti.
Any two friends, xi and yi, can be connected by zero or more tokens because if friends xi and yi share token ti and friends yi and zi also share token ti, then xi and zi are also said to share token ti.

Find the maximal product of xi and yi for any directly or indirectly connected (xi, yi) pair of friends such that xi and yi share the maximal number of tokens with each other.

Complete the maxTokens function in the editor. It has four parameters:

Name Type Description
friends_nodes integer The number of friends.
friends_from integer array Each friends_from[i] (where 0 ≤ i < friends_edges) denotes the first friend in pair (friends_from[i], friends_to[i]).
friends_to integer array Each friends_to[i] (where 0 ≤ i < friends_edges) denotes the second friend in pair (friends_from[i], friends_to[i]).
friends_weight integer array Each friends_weight[i] (where 0 ≤ i < friends_edges) denotes the ID number of a token shared by both friends_from[i] and friends_to[i].
Note: friends_edges is the number of pairs of friends that directly share a token.

The function must return an integer denoting the maximal product of xi and yi such that xi and yi are a pair of friends that share the maximal number of tokens with each other.

Input Format
The first line contains two space-separated integers describing the respective values of friends_nodes and friends_edges.
Each line i of the friends_edges subsequent lines (where 0 ≤ i < friends_edges) contains three space-separated integers describing the respective values of friends_fromi, friends_toi, and friends_weighti.

Constraints

2 ≤ friends_nodes ≤ 100
1 ≤ friends_edges ≤ min(200, (friends_nodes × (friends_nodes − 1)) / 2)
1 ≤ friends_weighti ≤ 100
1 ≤ friends_fromi, friends_toi ≤ friends_nodes
1≤ friends_weighti ≤ friends_edges
friends_fromi ≠ friends_toi
Each pair of friends can be connected by zero or more types of tokens.

Output Format
Return an integer denoting the maximal product of xi and yi such that xi and yi are a pair of friends that share the maximal number of tokens with each other.

Sample Input 0
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3

Sample Output 0
6

Explanation 0
Each pair of n = 4 friends is connected by the following tokens:

Pair (1, 2) shares 2 tokens (i.e., tokens 1 and 2)
Pair (1, 3) shares 1 token (i.e., token 1)
Pair (1, 4) shares 0 tokens
Pair (2, 3) shares 2 tokens (i.e., tokens 1 and 3)
Pair (2, 4) shares 1 token (i.e., token 3)
Pair (3, 4) shares 1 token (i.e., token 3)

The pairs connected by the maximal number of tokens are (1, 2) and (2, 3). Their respective products are 1 × 2 = 2 and 2 × 3 = 6. We then return the largest of these values as our answer, which is 6.

SuperCity consists of a single line of n buildings, where each building i is heighti units tall; however, SuperCity is under attack by two supervillains looking to show off their superpowers! The supervillains are standing on opposite ends of the city, unleashing their powers in an attempt to destroy all n buildings. In a single move, a supervillain unleashes their power and destroys the nearest contiguous block of buildings in which the respective heights of each building are nondecreasing. In other words:
If a supervillain is standing on the left end of the city and the nearest intact building is building i, then performing a move will destroy each consecutive building i, i + 1, i + 2, … satisfying heighti ≤ heighti+1 ≤ heighti+2 ≤ … until there are either no more buildings in their path or there is some building j satisfying heightj > heightj+1.
If a supervillain is standing on the right end of the city and the nearest intact building is building i, then performing a move will destroy each consecutive building i, i − 1, i − 2, … satisfying heighti ≤ heighti-1 ≤ heighti-2 ≤ … until there are either no more buildings in their path or there is some building j satisfying heightj > heightj-1.
Once a supervillain destroys a building, the building's height becomes 0.
Complete the function in the editor below. It has one parameter: an array of integers, height, where each heighti denotes the height of building i. The function must return an integer denoting the minimum number of total moves needed for two supervillains standing on opposite ends of the city (as described by the array of building heights) to destroy all n buildings.
Input Format
The first line contains an integer, n, denoting the number of elements in height.
Each line i of the n subsequent lines contains an integer describing heighti.
Constraints
1≤ n ≤ 105
1 ≤ heighti ≤ 105, where 0 ≤ i < n.
Output Format
Return an integer denoting the minimum number of total moves needed for two supervillains on opposite ends of the array to destroy all n buildings.
Sample Input 0
8
1
2
3
4
8
7
6
5
Sample Output 0
2
Explanation 0
The respective heights of each building are given as height = [1, 2, 3, 4, 8, 7, 6, 5]. The supervillains can perform the following minimal sequence of moves:
Sample Case 0
The diagram above depicts the changes to SuperCity's skyline after each move by a supervillain.
In the first move, the supervillain on the left destroys buildings 0 through 4, because height0 ≤ height1 ≤ height2 ≤ height3 ≤ height4; note that the destruction stops at this point, as height4 > height5.
In the second move, the supervillain on the right destroys buildings 7 through 5, because height7 ≤ height6 ≤ height5.
As it took a minimal two moves for the supervillains to level all the buildings, the function returns 2.
Sample Input 1
6
1
2
1
2
10
9
Sample Output 1
3
Explanation 1
The respective heights of each building are given as height = [1, 2, 1, 2, 10, 9]. The supervillains can perform the following minimal sequence of moves:
Sample Case 1
The diagram above depicts the changes to SuperCity's skyline after each move by a supervillain.
In the first move, the supervillain on the left destroys buildings 0 through 1, because height0 ≤ height1.
In the second move, the supervillain on the right destroys buildings 5 through 4, because height5 ≤ height4.
In the third move, the supervillain on the left destroys buildings 2 through 3, because height2 ≤ height3.
As it took a minimal three moves for the supervillains to level all the buildings, the function returns 3.