题

c.cpp/c/pas

• 时间限制：1.0s
• 内存限制：256MB
• 测试点数目：25

题目描述

由于出题人赶时间所以没办法编故事来作为背景。

一开始有 $n$ 个苹果，$m$ 个人依次来吃苹果，第 $i$ 个人会尝试吃 $u_i$ 或 $v_i$ 号苹果，具体来说分三种情况。

• 两个苹果都还在，那么这个人将随便选一个苹果吃了。
• 只有一个苹果，那么这个人将吃掉这个苹果。
• 都不在了，这个人吃不到苹果就走了。

请问有多少对苹果 $(i, j)\ (i < j)$ 满足它们两个都幸存下来的概率 $> 0$。

输入格式

第一行两个数 $n, m$。

接下来 $m$ 行，每行两个数 $u_i, v_i$。

输出格式

一个数表示答案。

样例输入

4 3
1 2
3 4
2 3

样例输出

1

样例解释

只有 $(1, 4)$ 满足条件。

数据范围

• 对于测试点 $1 \sim 5$：$n, m \le 20$。
• 对于测试点 $6 \sim 8$：若把苹果看做点，人看做边，那么会形成一棵树。
• 对于测试点 $9 \sim 15$：$m \le 400$。
• 对于测试点 $16 \sim 25$：无特殊限制。
• 对于所有的数据，$n \le 400$，$m \le 5 \times 10^4$。