#G1120. [GESP202506 七级] 线图

[GESP202506 七级] 线图

[GESP202506 七级] 线图

题目描述

给定由 nn 个结点与 mm 条边构成的简单无向图 GG,结点依次以 1,2,…,n1,2,\dots,n 编号。简单无向图意味着 GG 中不包含重边与自环。GG 的线图 L(G)L(G) 通过以下方式构建:

  • 初始时线图 L(G)L(G) 为空。
  • 对于无向图 GG 中的一条边,在线图 L(G)L(G) 中加入与之对应的一个结点。
  • 对于无向图 GG 中两条不同的边 (u1,v1),(u2,v2)(u_1,v_1),(u_2,v_2),若存在 GG 中的结点同时连接这两条边(即 u1,v1u_1,v_1 之一与 u2,v2u_2,v_2 之一相同),则在线图 L(G)L(G) 中加入一条无向边,连接 (u1,v1),(u2,v2)(u_1,v_1),(u_2,v_2) 在线图中对应的结点。

请你求出线图 L(G)L(G) 中所包含的无向边的数量。

输入格式

第一行,两个正整数 n,mn,m,分别表示无向图 GG 中的结点数与边数。

接下来 mm 行,每行两个正整数 ui,viu_i,v_i,表示 GG 中连接 ui,viu_i,v_i 的一条无向边。

输出格式

输出共一行,一个整数,表示线图 L(G)L(G) 中所包含的无向边的数量。

样例 #1

样例输入 #1

5 4
1 2
2 3
3 1
4 5

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

30

样例解释

原图 GG 中结点 1,2,31,2,3 构成一个三角形,结点 4,54,5 之间有一条独立边。对应的线图中,三角形三条边两两相邻形成三条线图边,独立边不与其他边相邻,故线图边数为 33。

数据范围

测试点占比 约束
60%60\% 的测试点 1≤n≤500, 1≤m≤5001 \le n \le 500,\ 1 \le m \le 500
所有测试点 1≤n≤105, 1≤m≤1051 \le n \le 10^5,\ 1 \le m \le 10^5