#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1 << 29 #define LL long long int LL const MOD = 1000000007; template class SegmentTree{ int n; int realsize; T initialvalue; vector tree; public: SegmentTree(int size,T initial):realsize(size),initialvalue(initial){ n = 1; while(n < size)n *= 2; tree = vector(2*n + 1,initial); } //1-indexed void insert(int i,T data){ int ind = n+i-1; tree[ind] = data; ind >>= 1; while(ind > 0){ tree[ind] = tree[ind*2] + tree[ind*2+1]; ind >>= 1; } } void add(int i,T data){ int ind = n+i-1; tree[ind] += data; ind >>= 1; while(ind > 0){ tree[ind] = tree[ind*2] + tree[ind*2+1]; ind >>= 1; } } T get(int l,int r){ if(l > realsize || r > realsize || l <= 0 || r <= 0)return initialvalue; l = n+l-1; r = n+r-1; if(l == r)return tree[l]; int prel = l; int prer = r; T lnum = tree[l]; T rnum = tree[r]; l >>= 1; r >>= 1; while(l != r){ if(l*2 == prel){ lnum += tree[l*2+1]; } if(r*2+1 == prer){ rnum += tree[r*2]; } prel = l; prer = r; l >>= 1; r >>= 1; } return lnum+rnum; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); LL n,m; cin >> n >> m; vector c(n); vector> a(n),b(n); for(int i = 0; i < n; i++){ LL x,y; cin >> x >> y; x++; y++; if(x > y){ swap(x,y); } a[i] = make_pair(x,(LL)i); b[i] = make_pair(y,(LL)i); c[i] = y; } sort(a.begin(),a.end()); sort(b.begin(),b.end()); LL t = 0; SegmentTree fr(n+1,0); for(int i = 0; i < n; i++){ t -= fr.get(upper_bound(b.begin(),b.end(),make_pair(c[a[i].second],(LL)INF)) - b.begin(),n+1); LL x = (LL)(upper_bound(b.begin(),b.end(),make_pair(a[i].first,(LL)0)) - b.begin()); if(x != 0){ t -= fr.get(1,x); } fr.add(lower_bound(b.begin(),b.end(),make_pair(c[a[i].second],(LL)0)) - b.begin() + 1,1); } cout << (n*(n-1))/2 + t << endl; return 0; }