Problem Description

Ladies and gentlemen.

Good morning, good afternoon, and good evening.

Welcome to the “So Good It Can’t Get Any Better! Terra Master Investment Class”. I am your Teacher Kan.

Not 10000, not 5000, only 999 Originium Ingots. One-on-one guidance, hands-on teaching, from beginner to expert, so that you can:

— Win every pick, hit every bet, quickly achieve financial freedom and become very rich!

Today’s location is — the Kazimierz Knight Tournament.

This tournament is a bit different. First, $N$ knights will form knight orders on their own, where knight $i$ will join knight order $a_i$.

Then, over the next $M$ days, each day two different knight orders $x$ and $y$ will be specified. After that, every member in knight order $x$ will duel once with every member in knight order $y$.

For each duel, we will place a bet. If the two knights’ indices are $a$ and $b$, then if your bet succeeds, you will get back your principal plus $a\times b$ Originium Ingots.

Of course, for each bet you must stake all your principal!

So, over the next $M$ days, under my guidance, how many Originium Ingots can you earn each day?

The data guarantees that the answer does not exceed the range of a 64-bit signed integer.

Gambling is risky. Invest with caution!

Input Format

The first line contains two positive integers $N$ ($1\le N \le 2\times 10^5$) and $M$ ($1\le M \le 2\times 10^5$), separated by spaces.

The next line contains $N$ positive integers $a_i$ ($1\le a_i \le 1\times 10^6$) separated by spaces, meaning that the knight with index $i$ belongs to the knight order with index $a_i$.

The next $M$ lines each contain two positive integers $x_i,y_i$ separated by spaces ($x_i \neq y_i$), and it is guaranteed that $x_i,y_i$ appear among $a_1 \sim a_n$.

Output Format

Output $M$ lines. Each line contains one positive integer. The $i$-th line represents the maximum profit obtainable on day $i$.

The data guarantees that the answer does not exceed the range of a 64-bit signed integer.

9 3
1 1 2 2 3 3 3 2 1
1 2
2 3
3 1

180
270
216

Hint

The members of knight order $1$ are $\{1,2,9\}$, the members of knight order $2$ are $\{3,4,8\}$, and the members of knight order $3$ are $\{5,6,7\}$.

On the first day, knight order $1$ and knight order $2$ compete.

The profit obtained is: $1\times 3+1\times 4+1\times 8+2\times 3+2\times 4+2\times 8+9\times 3+9\times 4+9\times 8=180$.

On the second day, knight order $2$ and knight order $3$ compete.

The profit obtained is: $3\times 5+3\times 6+3\times 7+4\times 5+4\times 6+4\times 7+8\times 5+8\times 6+8\times 7=270$.

On the third day, knight order $1$ and knight order $3$ compete.

The profit obtained is: $1\times 5+1\times 6+1\times 7+2\times 5+2\times 6+2\times 7+9\times 5+9\times 6+9\times 7=216$.

Translated by ChatGPT 5