D1 - Dual Friendship [Easy]

2 secs 1024 MB
uni_kakurenbo

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

問題文


から までの番号がついた 人の人がいて,さらに から までの番号がついた 個の友好関係があります.
友好関係 は人 と人 の間に友情があることを表し,「人 と人 とが互いに友達である」といいます.
ただし,自分同士と互いに友達であるような人は存在しません.

ここで「人 と人 とが友達の友達である」とは, 整数 が下記の条件を満たすことを指します.

  • 下記の条件をすべて満たす整数 が存在する
    • と人 とが互いに友達である
    • と人 とが互いに友達である

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

  • と人 友達の友達である

制約


  • ならば
  • 入力はすべて整数である

入力


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





出力


答えを出力せよ.

サンプル


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

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


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

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


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

入力例3 友好関係
のときに条件を満たします.

提出


Go (1.14)