Team Players
Contest: Educational Codeforces Round 44 (Rated for Div. 2)
Difficulty rating: 2700
Tags: combinatorics

There are $$$n$$$ players numbered from $$$0$$$ to $$$n-1$$$ with ranks. The $$$i$$$-th player has rank $$$i$$$.

Players can form teams: the team should consist of three players and no pair of players in the team should have a conflict. The rank of the team is calculated using the following algorithm: let $$$i$$$, $$$j$$$, $$$k$$$ be the ranks of players in the team and $$$i < j < k$$$, then the rank of the team is equal to $$$A \cdot i + B \cdot j + C \cdot k$$$.

You are given information about the pairs of players who have a conflict. Calculate the total sum of ranks over all possible valid teams modulo $$$2^{64}$$$.

Input format:
The first line contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — the number of players and the number of conflicting pairs.

The second line contains three space-separated integers $$$A$$$, $$$B$$$ and $$$C$$$ ($$$1 \le A, B, C \le 10^6$$$) — coefficients for team rank calculation.

Each of the next $$$m$$$ lines contains two space-separated integers $$$u_i$$$ and $$$v_i$$$ ($$$0 \le u_i, v_i < n, u_i \neq v_i$$$) — pair of conflicting players.

It's guaranteed that each unordered pair of players appears in the input file no more than once.

Output format:
Print single integer — the total sum of ranks over all possible teams modulo $$$2^{64}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example all $$$4$$$ teams are valid, i.e. triples: {0, 1, 2}, {0, 1, 3}, {0, 2, 3} {1, 2, 3}.

In the second example teams are following: {0, 2, 3}, {1, 2, 3}.

In the third example teams are following: {0, 1, 2}, {0, 1, 4}, {0, 1, 5}, {0, 2, 4}, {0, 2, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}.

Example input:
4 0
2 3 4

Example output:
64

Example input:
4 1
2 3 4
1 0

Example output:
38

Editorial:
Let's solve this task in several steps.
At first, let's calculate $$$all$$$ — sum of all triples. For each player $$$i$$$ consider three cases:
• $$$j<k<i$$$ — there are exactly $$${i}\choose{2}$$$ ways to choose triple;
• $$$j<i<k$$$ — there are $$$i \cdot (n-i-1)$$$ ways;
• $$$i<j<k$$$ — there are $$${n-i-1}\choose{2}$$$ ways.
At second, let's calculate $$$sub_1$$$ — sum over all triples $$$j<k<i$$$ such that exists pair $$$(j,i)$$$ or $$$(k,i)$$$. To calculate it we need for each $$$i$$$ iterate over all neighbors $$$x<i$$$ of $$$i$$$. Again some cases:
• if $$$x=j<k<i$$$ then there are exactly $$$(i-j-1)$$$ ways to choose $$$k$$$;
• if $$$j<x=k<i$$$, there are $$$x$$$ ways to choose $$$j$$$.
At third, let's calculate $$$sub_2$$$ — sum over all triple $$$j<k<i$$$ where exists pair $$$(j,k)$$$, but pairs $$$(j,i)$$$ and $$$(k,i)$$$ are not. $$$sub_2 = sub_2^0 - sub_2^1 - sub_2^2 + sub_2^{12}$$$.
• $$$sub_2^0$$$ is a sum of all triples $$$j<k<i$$$ where pair $$$(j,k)$$$ exists. It can be calculated while iterating $$$i$$$ in increasing order.
• $$$sub_2^1$$$ is a sum of all triples $$$j<k<i$$$ where pairs $$$(j,k)$$$ and $$$(j,i)$$$ exists. It can be calculated while iterating $$$(j,i)$$$ and asking sum on segment of adjacency list of $$$j$$$ ($$$O(1)$$$ with prefix sums for each vertex $$$j$$$).
• $$$sub_2^2$$$ is a sum of all triples $$$j<k<i$$$ where pairs $$$(j,k)$$$ and $$$(k,i)$$$ exists. It can be calculated while iterating $$$(k,i)$$$ and asking sum on prefix of adjacency list of $$$k$$$ (same $$$O(1)$$$).
• $$$sub_2^{12}$$$ is a sum of all triples $$$j<k<i$$$ where all pairs $$$(j,k)$$$, $$$(j,i)$$$ and $$$(k,i)$$$ exists. It is modification of calculating number of triangles in graph. It can be done in $$$O(M\sqrt{M})$$$ and will be explained below.
Then result $$$res = all - sub_1 - sub_2$$$.
The algorithm of finding all triangles in the given graph $$$G$$$ is following:
Let's call vertex heavy if $$$|G(v)| \ge \sqrt{M}$$$ and light otherwise. For each heavy vertex $$$v$$$ precalculate $$$has_v[i]$$$ — boolean array of adjacency of vertex $$$v$$$. It's cost $$$O(N \sqrt{M})$$$ of memory and time but memory can be reduced by using bitsets.
To calculate number of triangles $$$j<k<i$$$ let's iterate over $$$i$$$. There are two cases:
• if $$$i$$$ is heavy, then just iterate over all edges $$$(j,k)$$$ and check $$$has_i[j]$$$ and $$$has_i[k]$$$. This part works with $$$O(M\sqrt{M})$$$ time since there are $$$O(\sqrt{M})$$$ heavy vertices.
• if $$$i$$$ is light, then iterate over all pair $$$(j,k)$$$, where $$$j,k \in G(i)$$$ (at first fix $$$k$$$, then iterate $$$j<k$$$). To check existence of edge $$$(j,k)$$$ consider two more cases:   if $$$k$$$ is heavy, just check $$$has_k[j]$$$. It works in $$$O(1)$$$.  if $$$k$$$ is light, just check in some global array $$$curHas$$$ all neighbors of $$$k$$$, check all $$$j$$$ with $$$curHas[j]$$$ and uncheck neighbors of $$$k$$$. Checking in array $$$curHas$$$ require $$$O(|G(k)|)$$$ time and will be done $$$O(|G(k)|)$$$ times. So it will be $$$O(\sum{|G(v)|^2})=O(\sqrt{M}\sum{|G(v)|})=O(M\sqrt{M})$$$ in total.  Similarly, iterating pairs $$$j,k\in G(i)$$$ works with $$$O(\sum{|G(i)|^2})=O(M\sqrt{M})$$$ in total.
• if $$$k$$$ is heavy, just check $$$has_k[j]$$$. It works in $$$O(1)$$$.
• if $$$k$$$ is light, just check in some global array $$$curHas$$$ all neighbors of $$$k$$$, check all $$$j$$$ with $$$curHas[j]$$$ and uncheck neighbors of $$$k$$$. Checking in array $$$curHas$$$ require $$$O(|G(k)|)$$$ time and will be done $$$O(|G(k)|)$$$ times. So it will be $$$O(\sum{|G(v)|^2})=O(\sqrt{M}\sum{|G(v)|})=O(M\sqrt{M})$$$ in total.
So comlexity of algorithm and all task is $$$O(M\sqrt{M})$$$.