背景

GESP七级真题(202506)

描述

给定由 $n$ 个结点与 $m$ 条边构成的简单⽆向图 $G$ ，结点依次以 $1, 2, ..., n$ 编号。简单⽆向图意味着 $G$ 中不包含重边与⾃环。 $G$ 的线图 $L(G)$ 通过以下⽅式构建：

• 初始时线图 $L(G)$ 为空。
• 对于⽆向图 $G$ 中的⼀条边，在线图 $L(G)$ 中加⼊与之对应的⼀个结点。
• 对于⽆向图 $G$ 中两条不同的边 $(u_1, v_1), (u_2, v_2)$ ，若存在 $G$ 中的结点同时连接这两条边（即 $u_1, v_1$ 之⼀与 $u_2, v_2$ 之⼀相同），则在线图 $L(G)$ 中加⼊⼀条⽆向边，连接 $(u_1, v_1), (u_2, v_2)$ 在线图中对应的结点。

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

格式

输入

第⼀⾏，两个正整数 $n, m$ ，分别表⽰⽆向图 $G$ 中的结点数与边数。

接下来 $m$ ⾏，每⾏两个正整数 $u_i, v_i$ ，表⽰ $G$ 中连接 $u_i, v_i$ 的⼀条⽆向边。

输出

输出共⼀⾏，⼀个整数，表⽰线图 $L(G)$ 中所包含的⽆向边的数量。

样例

5 4
1 2
2 3
3 1
4 5

3

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

30

样例1解释

数据规模

对于 60 % 的测试点，保证 $1 \le n \le 500，1 \le m \le 500$。

对于所有测试点，保证 $1 \le n \le 10^5， 1 \le m \le 10^5$。

限制

时间限制：1.0 s

空间限制：512.0 MB