問題一覧 > 通常問題

No.488 四角関係

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 239
作問者 : 小指が強い人 / テスター : tatuyan_edson
2 ProblemId : 979 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-02-26 00:27:36

問題文

N個のノードが0番からN1番まで番号が割り当てられています。
そして、ノードは互いに関係を持っているノードもあれば持っていないノードもあります。
そのノードの集合の中で四角の関係を持つものの数を出力してください。
ここで言う四角の関係とは、4つのノードだけで考えた時、それが4点の閉路グラフであることを言います。
(その4点中の3点では閉路を作れないということである。)

入力

N M
a1 b1
a2 b2
  
aM1 bM1
aM bM

Nはノードの個数です。
Mは関係を持つノードの組の個数を表します。
aibiは、ノードの番号を表し、aibiに関係を持っていることを表します。
2N50 (整数)
1MN×(N1)2 (整数)
0ai<bi<N (整数)
(ai,bi)(aj,bj)
i=1...M

出力

X

問題文の答えを一つ出力してください。

サンプル

サンプル1
入力
6 8
0 1
1 2
2 3
0 2
0 3
3 4
4 5
0 5
出力
1


上の図は、サンプル1のノードの関係の図です。
{0,1,2,3}と{0,3,4,5}の2つですが、{0,1,2,3}は0と2に関係を持っているので除きます。
したがって、答えは1です。

サンプル2
入力
3 3
0 1
1 2
0 2
出力
0

3つのノードで四角の関係を持つことはありません。

サンプル3
入力
8 17
0 3
0 4
0 6
1 2
1 6
2 4
2 5
2 7
3 4
3 5
3 6
4 5
4 6
4 7
5 6
5 7
6 7
出力
3


{1,2,5,6},{1,2,7,6},{1,2,4,6}の3つが条件を満たします。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。