传统题 文件IO:friend 2000ms 1024MiB

乐队

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

D - 乐队

看了若干少女乐队番后你也想组乐队了。

现在你有 nn 位好友,你想在其中选出 44 位好友与你组成乐队 "KrygONic"。但你的好友之间关系不一定融洽。你不希望让乐队陷入不稳定的状态,所以你希望这 44 位朋友两两之间都是融洽的。

幸运的是你知道他们的交际关系。你知道在 (n2)\tbinom{n}{2} 个不同的关系中有 mm 组关系是融洽的。这 mm 组关系会在输入中给出。

现在你想知道,你能组成多少个不同的乐队?两个乐队不同当且仅当存在一个朋友在第一个乐队,但不在第二个乐队。

形式化题意:

给定一个 nn 个点 mm 条边的无向图,求选择四个不同的点的方案,使得它们两两之间有边。

输入格式

第一行包含两个整数 n,mn,m ,分别表示图的点数和边数。

接下来 mm 行,每行包含两个整数 u,vu,v,表示一条边的两个端点。

输出格式

输出一行一个整数,表示方案数。

样例

样例输入

5 9
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5

样例输出

2

数据范围

对于所有数据,1n,m21051\le n,m\le 2*10^51u<vn1\le u<v\le n 。保证没有重边。

子任务 1 ( 20% ) : n100n\le 100

子任务 2 ( 20% ) : m5000m\le 5000

子任务 3 ( 20% ) :n,m50000n,m\le 50000

子任务 4 ( 20% ) :n,m105n,m\le 10^5

子任务 5 ( 20% ) :无特殊限制。

11.22

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-11-22 8:00
结束于
2024-11-22 13:00
持续时间
5 小时
主持人
参赛人数
73