D1 - Dual Friendship [Easy]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

問題 D2 とは制約と内容が異なります

問題文

11 から NN までの番号がついた NN 人の人がいて,さらに 11 から MM までの番号がついた MM 個の友好関係があります.
友好関係 i(1iM)i \scriptsize \hspace{0.3em} (1 \leq i \leq M) は人 aia_i と人 bib_i の間に友情があることを表し,「人 aia_i と人 bib_i とが互いに友達である」といいます.
ただし,自分同士と互いに友達であるような人は存在しません.

ここで「人 ss と人 tt とが友達の友達である」とは,22 整数 s,t(1s,tN)s, t \scriptsize \hspace{0.3em} (1 \leq s, t \leq N) が下記の条件を満たすことを指します.

  • 下記の条件をすべて満たす整数 v(1vN)v \scriptsize \hspace{0.3em} (1 \leq v \leq N) が存在する
    • ss と人 vv とが互いに友達である
    • tt と人 vv とが互いに友達である

下記の条件をすべて満たす正整数の組 (p,q)(p, q) は何通りあるか,求めてください.

  • 1p<qN1 \leq p < q \leq N
  • pp と人 qq友達の友達である

制約

  • 1N30001 \leq N \leq 3000
  • 0Mmin{N(N1)2,3000}0 \leq M \leq \mathrm{min}\, \{\, \frac{N(N-1)}{2},\, 3000\,\}
  • 1ai<biN(1iM)1 \leq a_i < b_i \leq N \scriptsize \hspace{0.4em} (1 \leq i \leq M)
  • iji\neq j ならば (ai,bi)(aj,bj)(a_i, b_i)\neq(a_j, b_j)
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる.

NMN \hspace{0.5em} M
a1b1a_1 \hspace{0.5em} b_1
a2b2a_2 \hspace{0.5em} b_2
\vdots
aMbMa_M \hspace{0.5em} b_M

出力

答えを出力せよ.

サンプル

入力例1
4 3
1 2
2 3
2 4
出力例1
3

この友好関係を図に表すと次のようになります:
入力例1_友好関係
条件を満たす整数の組 (p,q)(p, q)(1,3),(1,4),(3,4)(1, 3), (1, 4), (3, 4) の計 33 つです.


入力例2
4 4
1 2
2 3
2 4
1 3
出力例2
5

入力例2 友好関係
(p,q)=(1,2),(1,3),(1,4),(2,3),(3,4)(p, q) = (1, 2), (1, 3), (1, 4), (2, 3), (3, 4) のときに条件を満たします.
互いに友達であるような 22 人が,同時に友達の友達であるような関係もあり得ることに注意してください.


入力例3
4 5
1 2
2 3
2 4
1 3
3 4
出力例3
6

入力例3 友好関係
(p,q)=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)(p, q) = (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) のときに条件を満たします.

提出


Go (1.21)