Public Judge

pjudge

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21729. 【CTS Round #1 Day 2】桥桥桥

Statistics

给定一张 $n$ 个点和 $m$ 条边的无向联通图 $G = (V, E)$,其中第 $i$($1 \le i \le m$)条边连接了顶点 $u_i$ 与 $v_i$($1 \le u_i, v_i \le n$)。

对于一个边集 $E$ 的子集 $E' \subseteq E$,如果在删除 $E'$ 后,存在两个顶点 $u, v \in V$ 满足 $u \ne v$,且顶点 $u$ 与 $v$ 在新图中不连通,则我们称 $E'$ 为图 $G$ 的一个割集。

你想要知道 $G$ 的边集 $E$ 的所有子集中,有多少个大小恰好为 $3$ 的割集。

输入格式

输入的第一行包含两个整数 $n$ 与 $m$,描述图的点数与边数。

接下来 $m$ 行,每行两个整数 $u, v$,描述一条边。图中可能包含重边,但不包含自环。

输出格式

输出一行一个整数,表示满足条件的集合的数量。

样例数据

样例 1 输入

3 3
1 2
1 3
2 3

样例 1 输出

1

样例 1 解释

合法的集合为:

  • $E' = \{ (1, 2), (1, 3), (2, 3) \}$。

样例 2 输入

5 7
1 2
1 3
1 4
2 3
2 4
3 4
4 5

样例 2 输出

19

样例 3 输入

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例 3 输出

0

样例 4 输入

3 4
1 2
1 2
2 3
2 3

样例 4 输出

4

子任务

对于所有数据,$2 \le n \le 2 \times 10^5$,$3 \le m \le 5 \times 10^5$。

对于所有数据,保证给出的图是一张连通无向图,可能包含重边,但不包含自环

子任务编号 $n \le$ $m \le$ 特殊性质 分值
$1$ $40$ $120$ $4$
$2$ $200$ $600$ $8$
$3$ $1\,000$ $3\,000$ $15$
$4$ $3\,000$ $10\,000$ $18$
$5$ $5 \times 10^4$ $1.5 \times 10^5$ $16$
$6$ $2 \times 10^5$ $5 \times 10^5$ A $18$
$7$ $21$
  • 性质 A:保证图是通过以下方式生成的:
    • 选定参数 $n, m$,满足 $n \in [2, 2 \times 10^5]$ 且 $m \in [\max(3, n - 1), \min\left(\binom n2, 5 \times 10^5\right)]$
    • 生成一棵 $n$ 个点的树。
    • 随机添加 $m-n+1$ 条非树边:每次从所有的 $(u, v)$ 中均匀随机选择一条边,使得这条边在加入图中后图中仍然不存在重边与自环。