g7-02630. GESP-7级-2025-06-线图

题目描述

给定由 $n$ 个结点与 $m$ 条边构成的简单无向图 $G$ ，结点依次以 $1, 2, \dots, 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)$ 中所包含的无向边的数量。

输入

输出

【样例解释 #1】

【数据范围】

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

对于所有测试点，保证 $1 \leq n \leq 1 0^{5}$ ， $1 \leq m \leq 1 0^{5}$ 。

来源：洛谷 P13017（CCF GESP 七级上机题）