← 返回题目列表

Codeforces · 421/D

D. 代码中的错误

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

最近在 FOS 代码中发现了一个严重的错误。 F公司的负责人想要找到罪魁祸首并惩罚他。为此,他召开了一次组织会议,问题是:谁窃听了代码?参加会议的 n 个编码员中的每一个都说:“我确信是 x 或 y 做到了!”

公司负责人决定选择两名嫌疑人并邀请他们到他的办公室。当然,他应该考虑编码员的意见。这就是为什么负责人想要做出这样的选择,至少n个编码员中的p个同意它。如果编码员在会议上指定的两个人中至少有一个被选为嫌疑人,则他同意对两名嫌疑人的选择。 F头有多少种方式选择两个嫌疑人?

请注意,即使某个编码员被选为嫌疑人,如果他在会议上指定了其他选定的编码员,他也可以同意领导的选择。

输入

第一行包含整数 n 和 p (3 ≤ n ≤ 3·105; 0 ≤ p ≤ n) — F 公司的编码人员数量以及约定的最少人数。

接下来的 n 行中的每一行都包含两个整数 xi, yi (1 ≤ xi, yi ≤ n) — 第 i 个编码器命名的编码器编号。保证 xi ≠ i、yi ≠ i、xi ≠ yi。

输出

打印一个整数——可能的两个可疑集合的数量。请注意,嫌疑对象的顺序并不重要,即集合 (1, 2) 和 (2, 1) 被认为是相同的。

示例

输入 #1

4 2
2 3
1 4
1 4
2 1

输出 #1

6

输入 #2

8 6
5 6
5 7
5 8
6 2
2 1
7 3
1 3
1 4

输出 #2

1