Submission

Score: 100

User: GGEZLOLx3D

Problemset: Tech Sprites

Language: cpp

Time: 1.401 second

Submitted On: 2026-03-25 17:54:58

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX 1e15
signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m,i,j,nn,t,en,mon,k,a,b,st,mod=1e9+7;
    cin >> n >> m;
    vector<pair<int,int>> arr(n+1);
    for(i=1;i<=n;i++){
        cin >> arr[i].first >> arr[i].second;
    }
    vector<pair<pair<int,int>,pair<int,int>>> par;
    vector<int> adj[n+1];
    for(i=0;i<m;i++){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vector<bool> vi(n+1,false);
    for(i=1;i<=n;i++){
        if(vi[i])continue;
        queue<int> bfs;
        bfs.push(i);
        vi[i]=true;
        vector<pair<int,int>> pp;
        while(!bfs.empty()){
            int x=bfs.front();
            pp.push_back(arr[x]);
            bfs.pop();
            for(int y:adj[x]){
                if(vi[y])continue;
                vi[y]=true;
                bfs.push(y);
            }
        }
        sort(pp.begin(),pp.end());
        pair<int,int> l={pp.front().first,pp.front().second},r={pp.back().first,pp.back().second};
        par.push_back({l,r});
    }
    sort(par.begin(),par.end());
    pair<int,int> mx=par[0].second;
    int ans=0;
    for(i=1;i<par.size();i++){
        if(par[i].first<mx){
            ans++;
        }
        mx=max(mx,par[i].second);
    }
    cout << ans;
}
/*
5 18 30
1 2 93 84 2
12 1261 0
LRRRRRRRRRRR

9 12 9
LURURDRUU

7 -4 3
RULUULD

7 2 7 4 9 3 3 5 8
5 2
0 1
2 2
3 6
6 6
9 10
10
15

5 2
0 0
2 0
7 0
4 0
10 0
10
3
*/