D.cpp

D.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#define intl long long
#define maxn 300100
using namespace std;

int i,j,k,l,m,n,a,b;
int mark[maxn],val[maxn],x[maxn],y[maxn];
map <int,int> wp[maxn];
map <int,int> :: iterator p;
intl ans;

int main() {
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i = 1; i <= n; i++) {
		scanf("%d %d",&x[i],&y[i]);
		val[x[i]]++; val[y[i]]++;
		wp[x[i]][y[i]]++; wp[y[i]][x[i]]++;
	}

	for (i = 1; i <= n; i++) mark[val[i]]++;
	for (i = n; i >= 0; i--) mark[i] += mark[i + 1];

	for (i = 1; i <= n; i++) {
		if (val[i] < m) {
			ans += (intl) mark[m - val[i]];
			if (val[i] >= m - val[i]) ans--;
		}
		else ans += (intl) (n - 1);
		for (p = wp[i].begin(); p != wp[i].end(); p++) {
			a = p -> first; b = p -> second;
			if (val[a] + val[i] >= m && val[a] + val[i] - b < m) ans--;
		}
	}

	cout << ans / 2;	
	return 0;
}