[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 $) の組の個数を出力せよ。
输入输出样例
输入样例 #1
3 1
1 2
输出样例 #1
2
输入样例 #2
4 3
1 2
3 4
2 3
输出样例 #2
1
输入样例 #3
3 2
1 2
1 2
输出样例 #3
0
输入样例 #4
10 10
8 9
2 8
4 6
4 9
7 8
2 8
1 8
3 4
3 4
2 7
输出样例 #4
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 $ 番目の男性が何もしない。