[AGC016E] Poor Turkeys

**题意:** 有 $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$ **输出:** 符合条件的数对数目

[problemUrl]: https://atcoder.jp/contests/agc016/tasks/agc016_e $ 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 $) の組の個数を出力せよ。

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 $ 番目の男性が何もしない。