Submission

Score: 10

User: NovemNotes

Problemset: Tech Sprites

Language: cpp

Time: 0.606 second

Submitted On: 2026-04-24 15:20:21

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6+2;

int n,m;
int head[N];
pair<int,int> p[N];
pair<int,int> g[N];

int fr(int n){
    return (head[n]==n? n : head[n]=fr(head[n]));
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> p[i].first >> p[i].second;
        g[i]={INT_MAX,INT_MIN};
    }
    int cnt=n;
    for(int i=1;i<=n;i++)head[i]=i;
    for(int i=1;i<=m;i++){
        int a,b;cin >> a >> b;
        int ha=fr(a),hb=fr(b);
        if(ha==hb)continue;
        head[ha]=hb;    
    }
    set<pair<int,int>> s;
    for(int i=1;i<=n;i++){
        int h=fr(i);
        // cout << i << " " << h << "\n";
        g[h].first = min(g[h].first,p[i].first);
        g[h].second = max(g[h].second,p[i].first);
    }
    for(int i=1;i<=n;i++){
        int h=fr(i);
        s.insert(g[h]);
    }
    // cout << "\n";
    int mx=0,ans=0;
    for(auto &[x,y]:s){
        if(mx>x){
            ans++;
        }else{
            mx=max(mx,y);
        }
        // cout << x << " " << y << "\n";
    }
    cout << ans << "\n";
    return 0;
}