← 返回题目列表

Codeforces · 985/G

G. 团队成员

中文机器翻译题面 查看原题

有 $$$n$$$ 玩家,编号从 $$$0$$$ 到 $$$n-1$$$ 并有等级。第 $$$i$$$ 玩家的排名为 $$$i$$$。

玩家可以组队:团队应由三名玩家组成,并且团队中的任何一对玩家都不应发生冲突。队伍的排名采用以下算法计算:设$$$i$$$、$$$j$$$、$$$k$$$为队伍中球员的排名,且$$$i < j < k$$$,则队伍的排名等于$$$A \cdot i + B \cdot j + C \cdot k$$$。

您将获得有关发生冲突的玩家对的信息。以 $$$2^{64}$$$ 为模计算所有可能的有效团队的排名总和。

输入

第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — 玩家数量和冲突对的数量。

第二行包含三个空格分隔的整数 $$$A$$$、$$$B$$$ 和 $$$C$$$ ($$$1 \le A, B, C \le 10^6$$$) — 团队排名计算的系数。

接下来的 $$$m$$$ 行包含两个以空格分隔的整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$0 \le u_i, v_i < n, u_i \neq v_i$$$) — 一对冲突的玩家。

保证每对无序的玩家在输入文件中出现不超过一次。

输出

打印单个整数 - 所有可能团队的排名总和以 $$$2^{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

注意

在第一个示例中,所有 $$$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}。