← 返回题目列表

Codeforces · 154/C

C. 双型材

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

一家开发大型社交网络的公司向您提供了一份工作。您的第一个任务是搜索最有可能属于同一用户的配置文件。

社交网络包含 n 个注册的个人资料,编号从 1 到 n。有些配对还有朋友(“友谊”关系是相互的,即如果i是j的朋友,那么j也是i的朋友)。假设配置文件 i 和 j (i ≠ j) 是双精度的,如果对于任何配置文件 k (k ≠ i, k ≠ j),两个陈述之一为真:k 是 i 和 j 的朋友,或者 k 不是它们中的任何一个的朋友。另外,i 和 j 可以是朋友,也可以不是朋友。

你的任务是计算不同无序对 (i, j) 的数量,使得配置文件 i 和 j 是双精度数。请注意,这些对是无序的,即对 (a, b) 和 (b, a) 被认为是相同的。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106), — 相应的个人资料数量和好友对数量。

接下来 m 行包含格式为“v u”的好友对的描述,其中 v 和 u (1 ≤ v, u ≤ n, v ≠ u) 是彼此为好友的个人资料的数量。保证每对无序的朋友不会出现超过一次,并且没有个人资料与其自身是朋友。

输出

打印单个整数 — 双精度型无序配置文件对的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 %I64d 说明符。

示例

输入 #1

3 3
1 2
2 3
1 3

输出 #1

3

输入 #2

3 0

输出 #2

3

输入 #3

4 1
1 3

输出 #3

2

注意

在第一个和第二个示例中,任何两个配置文件都是双精度的。

在第三个示例中,双打是配置文件对 (1, 3) 和 (2, 4)。