5082.BanG Dream! It's MyGO!!

时间限制:1s 内存限制:256MB

在“BanG Dream! It's MyGO!!!”的世界里,各个乐团的演出和排练场地像星星一样被连接在一起,形成了一张美丽的网络图。每个乐团都有自己独特的演出场地和练习室,这些地点通过各种路径互相连接,组成了一张复杂的图谱。

koala作为一名热爱音乐的乐团忠实粉丝,突然有了一个灵感。他想为最喜欢的乐团设计一个独特的徽章,这个徽章需要从网络图中找出一些特别的图案来代表乐团, 比如选三条边连接到一起, 具体来说,他对以下三种图案感兴趣:

  • 三角形:由三条边构成的连通子图,这是一种经典的图案。
  • 三芒星:四个点形成的图案,一个点连向其他三个点。
  • 闪电折线:一种特别的折线,由四个点按顺序连接, 即一条链。

koala想知道有多少种情况满足,你能帮帮他吗?

输入格式(从终端/标准输入读取)

第一行包合两个整数$n,m(1 ≤n ≤10^5,1≤m≤2 \times 10^5)$,依次表示无向图的点数和边数;
接下来 $m$ 行,每行两个整數$u,v(l ≤u,v≤n)$,表示一条边$(u,v)$。
题目保证无重边、自环。

输出格式(输出至终端/标准输出)

需要给出三条边的导出子图是连通的情况数量。由于答案可能很大,你只需要输出答案对$10^9+7$取模。

输入样例

复制
5 5
1 2
1 3
2 3
2 4
3 5
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n

输出样例

复制
8
 \n

说明

样例说明: 满足条件的导出子图的边集分别为:
$(1,2),(1,3),(2,3)$
$(1,2),(2,3),(2,4)$
$(1,3),(2,3),(3,5)$
$(1,2),(1,3),(2,4)$
$(1,2),(1,3),(3,5)$
$(2,4),(2,3),(3,5)$
$(1,3),(2,3),(2,4)$
$(1,2),(2,3),(3,5)$

来源: 河南萌新联赛2024第(六)场

提交题解

Please login first.

© 2025 FAQs