← 返回题目列表

AtCoder · agc016_e

E. 可怜的火鸡

中文机器翻译题面 查看原题

分数: 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