4248: 朋友关系
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
# New Friends
## 题目描述
有一个由$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$
输出
## 输出格式
输出所求答案。
样例输入 复制
4 3
1 2
2 3
1 4样例输出 复制
3提示
## 输入输出样例
### 输入样例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