U643948 你爱我,我爱你
题目描述
有 $n$ 头奶牛,编号从 $1$ 到 $n$,它们之间有 $m$ 对喜欢关系。
其中第 $i$ 对喜欢关系表示为两个整数 $u_i$ 和 $v_i$,它表示:
- 编号为 $u_i$ 的奶牛喜欢编号为 $v_i$ 的奶牛。
这种喜欢关系是单向的,即根据第 $i$ 对喜欢关系,我们只能得出“奶牛 $u_i$ 喜欢奶牛 $v_i$”,而不能得出“奶牛 $v_i$ 喜欢奶牛 $u_i$”。
这种喜欢关系具有传递性,即:
- 如果奶牛 $A$ 喜欢奶牛 $B$,而奶牛 $B$ 喜欢奶牛 $C$,则奶牛 $A$ 也喜欢奶牛 $C$。
请你根据这 $m$ 对喜欢关系,推导出有多少对奶牛相互喜欢。即统计存在多少下标对 $(x, y)$ 满足:
- $1 \le x \lt y \le n$,且
- 奶牛 $x$ 喜欢奶牛 $y$,且
- 奶牛 $y$ 喜欢奶牛 $x$。
输入格式
第一行,两个整数 $n$ 和 $m$,以空格分隔。
接下来 $m$ 行,每行包含两个整数 $u_i$ 和 $v_i$,表示奶牛 $u_i$ 喜欢奶牛 $v_i$。
输出格式
输出一个整数,表示相互喜欢的奶牛对数。
说明/提示
#### 样例 1 解释
一共有 $$ 对奶牛相互喜欢:
- 奶牛 $1$ 和奶牛 $2$ 相互喜欢;
- 奶牛 $1$ 和奶牛 $5$ 相互喜欢;
- 奶牛 $2$ 和奶牛 $5$ 相互喜欢。
#### 样例 2 解释
任意两头奶牛都相互喜欢。
#### 数据规模与约定
- 对于 $50\%$ 的数据,$n \le 1000, m \le 2000$
- 对于 $100\%$ 的数据,$1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5$,$1 \le u_i,v_i \le n$ 且 $u_i \neq v_i$ 且不存在重复的喜欢关系,即
- 若 $i \neq j$,则 $(u_i, v_i) \neq (u_j, v_j)$