No.1147 土偶Ⅱ
タグ : / 解いたユーザー数 79
作問者 : okazakisteve / テスター : kozy
問題文
土偶が$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もしくは右上の雲マークをクリックしてアカウントを作成してください。