AT_agc016_e [AGC016E] Poor Turkeys

有 $N$ 只鸟。这些鸟编号为 $1$ 到 $N$。 现在有 $M$ 个男人会依次到来。第 $i$ 个到来的男人会按如下方式行动： - 如果鸟 $x_i$ 和 $y_i$ 都还活着：他会以等概率选择其中一只吃掉。 - 如果这两只鸟中只有一只还活着：他会吃掉还活着的那只。 - 如果这两只鸟都已经不在了：他不会做任何事。 请你计算，满足下述条件的 $(i, j)\ (1\leq i

输入从标准输入读入，格式如下： > $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 翻译