Trout II

Hint: This problem isn't actually related to the original Trout task.

Unfortunately, dumping nuclear waste into the local river was a bad idea after all, and the trout population has most definitely been affected. The ecosystem has also been entirely transformed to the point that it is unrecognisable. There are now $N$ lakes numbered from $0$ to $N - 1$, which are connected by a series of $M$ channels where each channel runs between two different lakes $a_i$ and $b_i$. It is always possible for a trout to swim between any two lakes through some series of channels and lakes, and there is never more than one channel between a pair of lakes.

Due to concerningly high levels of background radiation (following a certain incident) the local trout population has gained intelligence, and the trout are now seeking revenge upon the Newfound Zealous Irradiating Corporation (NZIC). They have caught wind of a plan by the NZIC to begin fly fishing in these lakes soon. Naturally, the trout are unhappy about this and will not sit idly by this time around.

At each of the lakes the humans have constructed a warehouse to store exactly one type of lure. At the $i$-th lake lures of type $L_i$ will be stored. To manage the stock of lures the humans will need to move lures between warehouses that store the same type of lure. A shipment route is a series of connected channels between two lakes where the same type of lure is stored.

The trout have come up with a plan to sabotage exactly one channel which will make it so that no shipment route can pass through that particular channel. A shipment route is considered disrupted if it is no longer possible to move lures between a given pair of lakes. The trout are aiming to maximise the number of disrupted shipment routes. The trout have asked for your help to write a program to calculate the maximum number of possible shipment routes that can be disrupted by sabotaging exactly one channel. With your help the trout should be able to thwart the humans' fly fishing plans.

Input

The first line contains $N$ and $M$ separated by a space.

The second line contains $L_0, \dots, L_{N - 1}$, the type of lure stored at each lake.

The following $M$ lines contain $a_i$ and $b_i$ separated by a space, which are the endpoints of each channel.

Output

Output the maximum number of shipment routes that can be disrupted by sabotaging one channel.

Constraints

• $1 \le N \le 100,000$
• $N - 1 \le M \le 200,000$
• $0 \le L_i < 100,000$
• It is guaranteed that there is at most one channel between any two lakes.

Notes

• Python users should submit with Python 3.6 (PyPy 7.3) as this will generally make your solution run faster
• If you're using a type-sensitive language such as C, C++, C# or Java, you should use 64-bit integer types to prevent integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

Subtasks

• Subtasks 1 to 3: $M = N - 1$ and $a_i = i$ and $b_i = i + 1$ for $0 \le i < M$, that is the lakes are laid out in a row from $0$ through $N - 1$. The three subtasks only differ in the size of $N$:
  • Subtask 1 (20%): $N \le 100$
  • Subtask 2 (10%): $N \le 2,500$
  • Subtask 3 (10%) $N \le 100,000$
• Subtask 4 (20%): $M = N - 1$.
• Subtask 5 (25%): Every lake has the same type of lure.
• Subtask 6 (15%): No further constraints.

Sample Explanation

Sample 1

There is a shipment route between every pair of lakes with the same lure, so all the possible shipment route pairs are $(0, 2), (1, 3), (1, 4), (1, 6), (1, 7), (3, 4), (3, 6), (3, 7), (4, 6), (4, 7), (6, 7)$. By sabotaging the channel connecting lakes $4$ and $5$ it would be possible to sabotage six shipment routes: $(1, 6), (1, 7), (3, 6), (3, 7), (4, 6), (4, 7)$. This is the maximum possible number of shipment routes that can be disrupted by sabotaging a single edge. This sample would be a valid test case for all subtasks except Subtask 5.

Sample 2

The maximum possible number of disrupted shipment routes is achieved by sabotaging the channel between lakes $0$ and $2$. This sample would be a valid test case for Subtasks 4, 5, and 6.

Sample 3

The maximum possible number of disrupted shipment routes is achieved by sabotaging the channel between lakes $2$ and $3$. This sample would only be a valid test case for Subtask 6.