题目描述

有 $N$ 只鸟。这些鸟编号为 $1$ 到 $N$。

现在有 $M$ 个男人会依次到来。第 $i$ 个到来的男人会按如下方式行动：

• 如果鸟 $x_i$ 和 $y_i$ 都还活着：他会以等概率选择其中一只吃掉。
• 如果这两只鸟中只有一只还活着：他会吃掉还活着的那只。
• 如果这两只鸟都已经不在了：他不会做任何事。

请你计算，满足下述条件的 $(i, j)\ (1\leq i<j\leq N)$ 的组数有多少：

• 所有男人都行动结束后，鸟 $i$ 和鸟 $j$ 依然都存活的概率大于 $0$。

输入格式

输入从标准输入读入，格式如下：

$N$ $M$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_M$ $y_M$

输出格式

输出满足条件的 $(i, j)$ 对的组数。

样例 1

输入

3 1
1 2

输出

2

样例 2

输入

4 3
1 2
3 4
2 3

输出

1

样例 3

输入

3 2
1 2
1 2

输出

0

样例 4

输入

10 10
8 9
2 8
4 6
4 9
7 8
2 8
1 8
3 4
3 4
2 7

输出

5

说明/提示

限制条件

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

样例解释 1

只有 $(i, j) = (1, 3), (2, 3)$ 满足条件。

样例解释 2

只有 $(i, j) = (1, 4)$ 满足条件。鸟 $1$ 和 $4$ 都存活的情况如下：

• 第 $1$ 个男人吃掉了鸟 $2$。
• 第 $2$ 个男人吃掉了鸟 $3$。
• 第 $3$ 个男人什么也没做。

由 ChatGPT 5 翻译