CF420C.Bug in Code

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Recently 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 did it!'

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 coders agreed with it. A coder agrees with the choice of two suspects if at least one of the two people that he named at the meeting was chosen as a suspect. In how many ways can the head of F choose two suspects?

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.

最近在 FOS 代码中发现了一个严重漏洞。F 公司的负责人希望找出肇事者并予以惩处。为此,他召开了一次内部会议,议题是:“谁破坏了代码?” 会上,nn 名程序员中的每一位都声称:“我确信,要么 xx,要么 yy 干的!”

公司负责人决定从中挑选两名嫌疑人,并邀请他们到自己办公室。显然,他必须考虑程序员们的意见。因此,负责人希望做出一种选择,使得 nn 名程序员中至少有 pp 人同意该选择。一名程序员同意该选择,当且仅当他所指出的两人中至少有一人被选为嫌疑人。那么,负责人有多少种方式选出两名嫌疑人?

注意:即使某位程序员本人被选为嫌疑人,只要他在会上指出了另一位被选中的嫌疑人,他仍可视为同意负责人的选择。

输入格式

The first line contains integers n and p (3 ≤ n ≤ 3·105; 0 ≤ p ≤ n) — the number of coders in the F company and the minimum number of agreed people.

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

第一行包含两个整数 nn 和 pp(3 ≤ n ≤ 3⋅1053 \leq n \leq 3\cdot10^5;0 ≤ p ≤ n0 \leq p \leq n)—— 分别表示 F 公司的程序员人数以及至少需达成一致的人数。

接下来的 nn 行中,每行包含两个整数 xix_i、yiy_i(1 ≤ xi, yi ≤ n1 \leq x_i,\,y_i \leq n)—— 表示第 ii 位程序员所提名的两位程序员的编号。保证 xi ≠ ix_i \neq i,yi ≠ iy_i \neq i,且 xi ≠ yix_i \neq y_i。

输出格式

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) are considered identical.

输出一个整数——可能的两名嫌疑人的集合的数量。注意,嫌疑人的顺序无关紧要,即集合 (1, 2)(1,\,2) 和 (2, 1)(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

输入解题思路,AI测评打分。不知道怎么写?

首页