021 - Come Back in One Piece(★5) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 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

Source Name

「競プロ典型90問」21日目