分数: 1400 点
问题陈述
有 N 火鸡。 我们对它们进行编号 1 通过 N.
M 男人们将一一拜访这里。 的 i第一个来访的人将采取以下行动:
- 如果两只火鸡 x_i 和 y_i 活着:以相同的概率选择其中一个,然后吃掉它。
- 如果火鸡 x_i or y_i 是活的(但不是两者):吃掉活的。
- 如果火鸡都没有 x_i 也不 y_i 还活着:什么也不做。
查找对的数量 (i,\ j) (1 ≤ i < j ≤ N) 使得满足以下条件:
- 两只火鸡的概率 i 和 j 在所有的人采取行动后还活着,大于 0.
约束
- 2 ≤ N ≤ 400
- 1 ≤ M ≤ 10^5
- 1 ≤ x_i < y_i ≤ N
输入
输入由标准输入按以下格式给出:
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
(i,\ j) = (1,\ 3), (2,\ 3) 满足条件。
示例输入 2
4 3 1 2 3 4 2 3
示例输出 2
1
(i,\ j) = (1,\ 4) 满足条件。 两只火鸡 如果满足以下条件, 1 和 4 还活着:
- 第一个吃火鸡的人 2.
- 第二个人吃火鸡 3.
- 第三个人什么也没做。
示例输入 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