Submission

Score: 100

User: qweqwe

Problemset: Tech Sprites

Language: cpp

Time: 1.288 second

Submitted On: 2026-03-25 18:49:25

#include <bits/stdc++.h>
#define qweqwe cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

vector<int> parent(1000001);
vector<vector<int>> graph(1000001);

int find(int n){
	if (parent[n]==n) return n;
	return parent[n]=find(parent[n]);
}

int main(){
	qweqwe;
	int n,m;cin >> n >> m;
	parent.resize(n+1);
	iota(parent.begin(),parent.end(),0);
	vector<pii> arr(n+1);
	
	for (int i=1;i<=n;i++){
		cin >> arr[i].first >> arr[i].second;
	}
	
	for (int i=0;i<m;i++){
		int u,v;cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	/*
	unordered_set<int> u;
	for (int i=1;i<=n;i++){
		u.insert(parent[i]);
	}cout << u.size()-1;
	*/
	
	int mn=0;
	vector<bool> vis(1000001,0);
	vector<pair<pii,pii>> wow;
	
	for (int i=1;i<=n;i++){
		if (vis[i]) continue;
		queue<int> q;
		vector<pii> mambo;
		q.push(i);
		
		//cout << i.first << " " << i.second.first.first << " " << i.second.first.second << " " << i.second.second.first << " " << i.second.second.second << "\n";
		
		while (!q.empty()){
			int cur=q.front();q.pop();
			mambo.push_back(arr[cur]);
			
			//if (u.count(cur)) continue;
			//u.insert(cur);
			
			//cout << i.first << " " << cur << "\n";
			
			for (int j:graph[cur]){
				if (vis[j]) continue;
				vis[j]=1;
				q.push(j);
			}
		}
		sort(mambo.begin(),mambo.end());
		
		pii mn=mambo[0],mx=mambo[mambo.size()-1];
		wow.push_back({mn,mx});
	}
	sort(wow.begin(),wow.end());
	pii cur = wow[0].second;
	
	int cnt=0;
	for (int i=1;i<wow.size();i++){
		
		if (wow[i].first < cur){
			cnt++;
		}cur=max(cur,wow[i].second);
	}cout << cnt;
	
	/*
	for (pair<int,vector<pii>> i:pos){
		cout << i.first << "\n";
		for (pii j:i.second){
			cout << j.first << " " << j.second << '\n';
		}cout << "\n--------------\n";
	}
	*/
	
	
	return 0;
}