No.488 四角関係

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 122
作問者 : 小指が強い人小指が強い人 / テスター : tatuyan_edsontatuyan_edson

1 ProblemId : 979 / 出題時の順位表

問題文

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

入力

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$⋮$  $⋮$
$a_{M-1}$ $b_{M-1}$
$a_M$ $b_M$

$N$はノードの個数です。
$M$は関係を持つノードの組の個数を表します。
$a_i$と$b_i$は、ノードの番号を表し、$a_i$と$b_i$に関係を持っていることを表します。
$2 \le N \le 50$ (整数)
$1 \le M \le \frac{N \times (N - 1)}{2}$ (整数)
$0 \le a_i < b_i < N$ (整数)
$(a_i,b_i) \ne (a_j,b_j)$
$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つが条件を満たします。

提出ページヘ