codeforces 420C. Bug in Code

codeforces 420C. Bug in Code

​​a serious bug has been found in the FOS code. The head of the F company wants to find the culprit and punish him. For that, he set up an organizational meeting, the issue is: who's bugged the code? Each of the n coders on the meeting said: 'I know for sure that either x or y

The head of the company decided to choose two suspects and invite them to his office. Naturally, he should consider the coders' opinions. That's why the head wants to make such a choice that at least p of n

Note that even if some coder was chosen as a suspect, he can agree with the head's choice if he named the other chosen coder at the meeting.

Input

The first line contains integers n and p (3 ≤ n ≤ 3·105; 0 ≤ p ≤ n)

Each of the next n lines contains two integers xi, yi (1 ≤ xi, yi ≤ n) — the numbers of coders named by the i-th coder. It is guaranteed that xi ≠ i,  yi ≠ i,  xi ≠ yi.

Output

Print a single integer –– the number of possible two-suspect sets. Note that the order of the suspects doesn't matter, that is, sets (1, 2) и (2, 1)

Sample test(s)

Input

4 2 2 3 1 4 1 4 2 1

Output

6

Input

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

Output

1

贴一张图辅助说明：

设A和B被指认为嫌疑人的频度是agree[a]，agree[b]，被人同时认定是嫌疑人的频度是map(a,b)，那么A和B影响的对数是P=agree[a]+agree[b]-map(a,b)。假如P>=k就算入结果中。为了快速统计结果，可以先放两个指针p, pp在排好序（从小到大）的agree数组左右两边，p每向右移动一位，pp不断向左移动，直到agree[p]+agree[pp]=k），迭代下去。。。通过此法算出总的个数（agree[a]+agree[b]>=k），然后减去P=agree[a]+agree[b]-map(a,b)

#include #include #include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。