AT_agc016_e.[AGC016E] Poor Turkeys

有 $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)$ 对的组数。

限制条件

• $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 翻译