CF985G.Team Players

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are nn players numbered from 00 to n1n-1 with ranks. The ii -th player has rank ii .

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 ii , jj , kk be the ranks of players in the team and i<j<ki < j < k , then the rank of the team is equal to Ai+Bj+CkA \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 2642^{64} .

输入格式

The first line contains two space-separated integers nn and mm ( 3n21053 \le n \le 2 \cdot 10^5 , 0m21050 \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 AA , BB and CC ( 1A,B,C1061 \le A, B, C \le 10^6 ) — coefficients for team rank calculation.

Each of the next mm lines contains two space-separated integers uiu_i and viv_i ( 0ui,vi<n,uivi0 \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.

输出格式

Print single integer — the total sum of ranks over all possible teams modulo 2642^{64} .

输入输出样例

  • 输入#1

    4 0
    2 3 4
    

    输出#1

    64
    
  • 输入#2

    4 1
    2 3 4
    1 0
    

    输出#2

    38
    
  • 输入#3

    6 4
    1 5 3
    0 3
    3 5
    5 4
    4 3
    

    输出#3

    164
    

说明/提示

In the first example all 44 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}.

首页