English · Original
Chinese · Translation
Formal · Original
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
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
Print single integer — the total sum of ranks over all possible teams modulo $2^{64}$.
[samples]
## 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}.
有 $n$ 名玩家，编号从 $0$ 到 $n -1$，每位玩家的排名为其编号。第 $i$ 名玩家的排名为 $i$。
玩家可以组成团队：每个团队必须由三名玩家组成，且团队中任意两名玩家之间不得存在冲突。团队的排名按以下算法计算：设团队中三名玩家的排名分别为 $i$、$j$、$k$，且满足 $i < j < k$，则该团队的排名为 $A \dotop i + B \dotop j + C \dotop k$。
你将获得所有存在冲突的玩家对的信息。请计算所有可能的有效团队的排名总和，结果对 $2^{64}$ 取模。
第一行包含两个用空格分隔的整数 $n$ 和 $m$（$3 \leq n \leq 2 \dotop 10^5$，$0 \leq m \leq 2 \dotop 10^5$），分别表示玩家数量和冲突对的数量。
第二行包含三个用空格分隔的整数 $A$、$B$ 和 $C$（$1 \leq A, B, C \leq 10^6$），表示计算团队排名的系数。
接下来的 $m$ 行，每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$0 \leq u_i, v_i < n$，$u_i \neq v_i$），表示一对存在冲突的玩家。
保证输入文件中每个无序玩家对最多只出现一次。
请输出一个整数——所有可能的有效团队的排名总和对 $2^{64}$ 取模的结果。
在第一个示例中，所有 $4$ 个团队都是有效的，即三元组：{0, 1, 2}、{0, 1, 3}、{0, 2, 3}、{1, 2, 3}。
在第二个示例中，有效的团队为：{0, 2, 3}、{1, 2, 3}。
在第三个示例中，有效的团队为：{0, 1, 2}、{0, 1, 4}、{0, 1, 5}、{0, 2, 4}、{0, 2, 5}、{1, 2, 3}、{1, 2, 4}、{1, 2, 5}。
## Input
第一行包含两个用空格分隔的整数 $n$ 和 $m$（$3 \leq n \leq 2 \dotop 10^5$，$0 \leq m \leq 2 \dotop 10^5$），分别表示玩家数量和冲突对的数量。第二行包含三个用空格分隔的整数 $A$、$B$ 和 $C$（$1 \leq A, B, C \leq 10^6$），表示计算团队排名的系数。接下来的 $m$ 行，每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$0 \leq u_i, v_i < n$，$u_i \neq v_i$），表示一对存在冲突的玩家。保证输入文件中每个无序玩家对最多只出现一次。
## Output
请输出一个整数——所有可能的有效团队的排名总和对 $2^{64}$ 取模的结果。
[samples]
## Note
在第一个示例中，所有 $4$ 个团队都是有效的，即三元组：{0, 1, 2}、{0, 1, 3}、{0, 2, 3}、{1, 2, 3}。在第二个示例中，有效的团队为：{0, 2, 3}、{1, 2, 3}。在第三个示例中，有效的团队为：{0, 1, 2}、{0, 1, 4}、{0, 1, 5}、{0, 2, 4}、{0, 2, 5}、{1, 2, 3}、{1, 2, 4}、{1, 2, 5}。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of players, numbered $ 0 $ to $ n-1 $, where player $ i $ has rank $ i $.
Let $ m \in \mathbb{Z} $ be the number of conflicting unordered pairs.
Let $ A, B, C \in \mathbb{Z}^+ $ be fixed coefficients.
Let $ E \subseteq \binom{[n]}{2} $ be the set of conflicting pairs, where $ [n] = \{0, 1, \dots, n-1\} $.
A valid team is a triple $ \{i, j, k\} \in \binom{[n]}{3} $ such that no pair in $ \{\{i,j\}, \{i,k\}, \{j,k\}\} $ belongs to $ E $.
For a valid team with ranks $ i < j < k $, its rank is defined as:
$$
R(i,j,k) = A \cdot i + B \cdot j + C \cdot k
$$
**Constraints**
1. $ 3 \leq n \leq 2 \cdot 10^5 $
2. $ 0 \leq m \leq 2 \cdot 10^5 $
3. $ 1 \leq A, B, C \leq 10^6 $
4. Each conflicting pair $ \{u_i, v_i\} \in E $ satisfies $ u_i \ne v_i $, and all pairs are distinct.
**Objective**
Compute:
$$
\sum_{\substack{\{i,j,k\} \in \binom{[n]}{3} \\ \text{no pair in } E}} \left( A \cdot i + B \cdot j + C \cdot k \right) \mod 2^{64}
$$
where $ i < j < k $ in each triple.
API Response (JSON)
{
"problem": {
"name": "G. Team Players",
"description": {
"content": "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 s",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF985G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There are $n$ players numbered from $0$ to $n-1$ with ranks. The $i$\\-th player has rank $i$.\n\nPlayers can form teams: the team should consist of three players and **no pair** of players in the team s...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "有 $n$ 名玩家，编号从 $0$ 到 $n -1$，每位玩家的排名为其编号。第 $i$ 名玩家的排名为 $i$。\n\n玩家可以组成团队：每个团队必须由三名玩家组成，且团队中任意两名玩家之间不得存在冲突。团队的排名按以下算法计算：设团队中三名玩家的排名分别为 $i$、$j$、$k$，且满足 $i < j < k$，则该团队的排名为 $A \\dotop i + B \\dotop j + C \\doto...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of players, numbered $ 0 $ to $ n-1 $, where player $ i $ has rank $ i $. \nLet $ m \\in \\mathbb{Z} $ be the number of conflicting unordered pai...",
"is_translate": false,
"language": "Formal"
}
]
}