Submission

Score: 0

User: qweqwe

Problemset: Tech Sprites

Language: cpp

Time: 2.595 second

Submitted On: 2026-03-25 18:31:06

#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);

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);
	
	for (int i=0;i<n;i++){
		cin >> arr[i].first >> arr[i].second;
	}
	
	for (int i=0;i<m;i++){
		int u,v;cin >> u >> v;
		int pu=find(u),pv=find(v);
		if (pu!=pv){
			parent[pv]=parent[pu];
		}
	}
	/*
	unordered_set<int> u;
	for (int i=1;i<=n;i++){
		u.insert(parent[i]);
	}cout << u.size()-1;
	*/
	
	unordered_map<int,pair<pii,pii>> pos;
	for (int i=1;i<=n;i++){
		if (!pos.count(parent[i])){
			pos[parent[i]]={{INT_MAX,INT_MAX},{INT_MIN,INT_MIN}};
		}
		
		pii a=pos[parent[i]].first,b=pos[parent[i]].second;
		pii cur=arr[i-1];
		
		if (a.first > cur.first || (a.first==cur.first && a.second >= cur.second)){
			pos[parent[i]].first=cur;
		}
		if (b.first < cur.first || (b.first==cur.first && b.second <= cur.second)){
			pos[parent[i]].second=cur;
		}
	}
	int mn=0;
	for (pair<int,pair<pii,pii>> i:pos){
		unordered_set<int> u;
		queue<pair<int,pair<pii,pii>>> q;
		q.push(i);
		int cnt=0;
		
		//cout << i.first << " " << i.second.first.first << " " << i.second.first.second << " " << i.second.second.first << " " << i.second.second.second << "\n";
		
		while (!q.empty()){
			pair<int,pair<pii,pii>> t=q.front();
			int cur=q.front().first;q.pop();
			
			//if (u.count(cur)) continue;
			//u.insert(cur);
			
			//cout << i.first << " " << cur << "\n";
			
			for (pair<int,pair<pii,pii>> j:pos){
				
				//cout << j.first << " ";
				if (t.first==j.first) continue;
				if (u.count(j.first)) continue;
				
				int mna=t.second.first.first,mnb=t.second.first.second;
				int mxa=t.second.second.first,mxb=t.second.second.second;
				int c1 = j.second.first.first,c2 = j.second.first.second;
				int c3 = j.second.second.first,c4 = j.second.second.second;
				
				u.insert(j.first);
				bool yes=0;
				if (mna > c1 || (mna==c1 && mnb >= c2)){
					q.push({j.first,{{mna,mnb},{c3,c4}}});yes=1;
				}if (mxa < c3 || (mxa==c3 && mxb <= c4)){
					q.push({j.first,{{c1,c2},{mxa,mxb}}});yes=1;
				}
				if (!yes)cnt++;
				//cout << "yeah\n";
				q.push({j.first,{{c1,c2},{c3,c4}}});
			}
		}
		//cout << i.first << " " << cnt << '\n';
		mn=max(mn,cnt);
	}cout << mn;
	/*
	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;
}