题目描述

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

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

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

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

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

输入格式

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

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

输出格式

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

题目大意

题意:
有 $N(2<=N<=400)$ 只火鸡, 编号为 $1$ 到 $N$ , 有 $M(1<=M<=10^5)$ 个人, 每人指定了两只火鸡 $x$ 和 $y$ .
1.若 $x$ 和 $y$ 都活着, 那么这个人将会等概率地随机吃掉一只
2.若 $x$ 和 $y$ 恰好活着一只, 那么这个人将会吃掉活着的这只
3.若 $x$ 和 $y$ 都已经死亡, 那么只好什么都不做
注意，第 $1$ 个人到第 $M$ 个人每个人依次行动
求有多少个 $(i,j)(1<=i<j<=N)$ 满足在最终时刻第 $i$ 只火鸡和第 $j$ 只火鸡可能都还活着
输入:
第一行 $N,M$ ,接下来 $M$ 行,每行对应一个 $x_i,y_i$
输出:
符合条件的数对数目

3 1
1 2

2

4 3
1 2
3 4
2 3

1

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

$(i,\ j)\ =\ (1,\ 4)$ が条件を満たします。 鳥 $1$, $4$ が両方とも生き残るのは、次のような場合です。 - $1$ 番目の男性が鳥 $2$ を食べる。 - $2$ 番目の男性が鳥 $3$ を食べる。 - $3$ 番目の男性が何もしない。