4248: New Friends

# New Friends ### 内存 1024MB ### 时间 2S ## 题目描述 有一个由$N$个用户使用的社交网络,用户编号从$1$到$N$。在这个社交网络中,两个用户可以成为"朋友"。朋友关系是双向的;如果用户$X$是用户$Y$的朋友,那么用户$Y$也一定是用户$X$的朋友。 目前,社交网络上有$M$对朋友关系,第i对朋友关系由用户$A_i$和$B_i$组成。 请确定以下操作最多可以执行多少次: - 操作:选择三个用户$X$、$Y$和$Z$,使得$X$和$Y$是朋友,$Y$和$Z$是朋友,但$X$和$Z$不是朋友。然后让$X$和$Z$成为朋友。 ## 输入格式 输入从标准输入中以下列格式给出: $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 4 3 1 2 2 3 1 4 ``` ### 输出样例1 ``` 3 ``` ### 输入样例2 ``` 3 0 ``` ### 输出样例2 ``` 0 ``` ### 输入样例3 ``` 10 8 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 ``` ### 输出样例3 ``` 12 ``` ## 数据范围与提示 【样例1说明】 可以发生三次新的朋友关系,如下: - 用户1与用户3成为朋友,3是1的朋友(用户2)的朋友 - 用户3与用户4成为朋友,4是3的朋友(用户1)的朋友 - 用户2与用户4成为朋友,4是2的朋友(用户1)的朋友 不可能有四次或更多的新朋友关系。 【样例2说明】 如果最初没有朋友关系,就不可能产生新的朋友关系。 【数据范围】 - $2 \leq N \leq 2 \times 10^5$ - $0 \leq M \leq 2 \times 10^5$ - $1 \leq A_i < B_i \leq N$ - $(A_i, B_i)$对是互不相同的。 - 所有输入值都是整数。 ## 题目来源 ABC350D