問題一覧 > 通常問題

No.1147 土偶Ⅱ

レベル : / 実行時間制限 : 1ケース 0.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : okazakisteveokazakisteve / テスター : kozykozy
5 ProblemId : 4918 / 自分の提出
問題文最終更新日: 2020-08-06 09:24:23

問題文

土偶が$n$体が一列に並んでいます。
今、土偶同士の友達関係が$m$組与えられます。また、「良い関係」とは、次のように定義します。
・「良い関係」にある土偶は、友達の友達関係ではない。
・友達の友達には、自分や自分の友達は含まれない。
あなたは土偶たちの中から3体を選んで捨てたいです。しかし、捨てる3体の土偶の中でどの2体も「よい関係」 でないと呪われます。 あなたは呪われたくありませんので、気を付けて3体を選ぶ必要があります。そのような選び方は何通りですか?
例えば、3体の土偶がそれぞれ左から2,4,5番目であるとき、(2,5,4)と(2,4,5)は区別しません。

入力

$n \ m$
$a_1 \ b_1$
$a_2 \ b_2$
$\vdots$
$a_m \ b_m$

$3 \leq n \leq 100$、$1 \leq m \leq \dfrac{n(n-1)}{2}$
3行目以降の$m$行では、左から$a_i$番目の土偶と$b_i$番目の土偶が友達関係にあることを表しています($a_i \neq b_i$)。このことは、複数回言及される可能性もあります。 $1 \leq a_i,b_i \leq n$であり、入力はすべて整数です。

出力

捨てる土偶の選び方の通り数を一行に出力してください。
最後に改行してください。
追記:出力の内容を一部訂正しました。(2020/8/5-19:00)

サンプル

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

サンプル2
入力
5 2
4 5
3 5
出力
7

3と4が友達の友達関係です。

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

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