配点 : $1400$ 点

問題文

$N$ 羽の鳥がいます。 鳥には $1$ から $N$ まで番号が振られています。

ここに $M$ 人の男性が一人ずつ順番に訪れます。 $i$ 番目に訪れる男性は次のような行動をします。

• 鳥 $x_i$, $y_i$ が両方とも生き残っている場合 : 鳥 $x_i$, $y_i$ の一方を等確率で選んで食べる。
• 鳥 $x_i$, $y_i$ の一方のみが生き残っている場合 : 生き残っている方の鳥を食べる。
• 鳥 $x_i$, $y_i$ がどちらも生き残っていない場合 : 何もしない。

次の条件を満たす $(i,\ j)$ ($1 \leq i < j \leq N$) の組の個数を求めてください。

• すべての男性が行動を終えた後、鳥 $i$, $j$ が両方とも生き残っている確率が $0$ より大きい。

制約

• $2 \leq N \leq 400$
• $1 \leq M \leq 10^5$
• $1 \leq x_i < y_i \leq N$

入力

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

$N$ $M$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_M$ $y_M$

出力

条件を満たす $(i,\ j)$ ($1 \leq i < j \leq N$) の組の個数を出力せよ。

3 1
1 2

2

$(i,\ j) = (1,\ 3), (2,\ 3)$ が条件を満たします。

4 3
1 2
3 4
2 3

1

$(i,\ j) = (1,\ 4)$ が条件を満たします。 鳥 $1$, $4$ が両方とも生き残るのは、次のような場合です。

• $1$ 番目の男性が鳥 $2$ を食べる。
• $2$ 番目の男性が鳥 $3$ を食べる。
• $3$ 番目の男性が何もしない。

3 2
1 2
1 2

0

10 10
8 9
2 8
4 6
4 9
7 8
2 8
1 8
3 4
3 4
2 7

5