← 返回题目列表

AtCoder · typical90_u

021. 一体归来(★5)

中文机器翻译题面 查看原题

配点: 5 点

問題文

N 頂点 M 边的有向图。在侧面 它的编号为 1,2,\dots,M ,边缘 i 是顶点 A_i 到顶点 前往 B_i 。

满足以下条件 2 頂点 (x, y) 对 有多少个 (1 \leq x \lt y \leq N) ? 到

  • 頂点 x 到顶点 前往 y 的路径,顶点 两条路径都通往 y 到顶点 前往 x 两条路径都存在。

制約

  • 2 \leq N \leq 100000
  • 1 \leq M \leq 200000
  • 1 \leq A_i , B_i \leq N (1 \leq i \leq M)
  • A_i \ne B_i (1 \leq i \leq M)
  • 所有输入均为整数

入力

输入如下格式从标准输入给出。

N M
A_1 B_1
A_2 B_2
 \vdots 
A_M B_M

出力

请输出答案。


入力例 1

4 7
1 2
2 1
2 3
4 3
4 1
1 4
2 3

出力例 1

3

例如,(x,y) = (1,2) 是顶点 1 到顶点 前往 2 到边缘 由 1 组成的路径是一个顶点 由于获得了由 2 到顶点 前往 1 到边缘 由 2 组成的路径,因此满足条件。 除此之外 (x,y)=(1,4),(2,4) 满足条件,但是(x,y)=(2,3) 是顶点 由于 3 到顶点 前往 2 的路径不存在,因此不满足条件。

此外,边缘 请注意,它可能包含多个边,例如 3 和边缘 由 7 。


入力例 2

100 1
1 2

出力例 2

0