求给定无向图对应线图的无向边数量

时间限制

1.0 s

内存限制

512.0 MB

题目描述

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

1. 初始时线图L(G)为空。
2. 对于无向图G中的一条边，在线图L(G)中加入与之对应的一个结点。
3. 对于无向图G中两条不同的边(u1,v1),(u2,v2)，若存在公共结点，则在线图L(G)中加入一条无向边，连接两条边对应的结点。 请你求出线图L(G)中所包含的无向边的数量。

   输入格式

   第一行，两个正整数n,m，分别表示无向图G中的结点数与边数。 接下来m行，每行两个正整数u_i,v_i，表示G中连接u_i,v_i的一条无向边。

   输出格式

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

   样例

   输入样例1

   5 4
   1 2
   2 3
   3 1
   4 5

   输出样例1

   3

   输入样例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

   样例解释1

   图片内容：[样例示意图：左为原图G包含三角形(1-2-3-1)和独立边4-5，右为对应线图L(G)有3条边]

   数据范围

   图片内容：[对于60%的测试点，保证 1 ≤ n ≤ 500，1 ≤ m ≤ 500；对于所有测试点，保证 1 ≤ n ≤ 10^5，1 ≤ m ≤ 10^5]