#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 100005;
int n;
int cnt;
vector<int> v[MAXN];
int tata[MAXN];
int dim[MAXN];
// Array-uri noi pentru optimizari
int global_comp[MAXN];
int R_block[MAXN];
int max_reach_node[MAXN];
int comp_max_reach[MAXN];
// Priority queue pentru a scoate eficient minimul din "max_reach" al componentelor active
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int rad(int x) {
if(x == tata[x]) return x;
return tata[x] = rad(tata[x]);
}
void uneste(int x, int y) {
int rx = rad(x);
int ry = rad(y);
if(rx == ry) return;
if(dim[rx] < dim[ry]) {
swap(rx, ry);
}
cnt--;
tata[ry] = rx;
dim[rx] += dim[ry];
// Noul reach maxim este maximul dintre cele doua
comp_max_reach[rx] = max(comp_max_reach[rx], comp_max_reach[ry]);
// Adaugam noul root in priority queue
pq.push({comp_max_reach[rx], rx});
}
// Folosim BFS pentru a evita stack overflow
void bfs_comp(int start_node, int c_id) {
queue<int> q;
q.push(start_node);
global_comp[start_node] = c_id;
while(!q.empty()) {
int node = q.front();
q.pop();
for(int nxt : v[node]) {
if(!global_comp[nxt]) {
global_comp[nxt] = c_id;
q.push(nxt);
}
}
}
}
vector<int> partition_players(int N, int M, vector<int> X, vector<int> Y) {
n = N;
// Curatam structurile in cazul in care functia e rulata pe mai multe teste succesive
for(int i = 1; i <= n; i++) {
v[i].clear();
global_comp[i] = 0;
}
for(int i = 0; i < M; i++) {
int a = X[i] + 1;
int b = Y[i] + 1;
v[a].push_back(b);
v[b].push_back(a);
}
// 1. Gasim componentele conexe in graful complet
int c_id = 0;
for(int i = 1; i <= n; i++) {
if(!global_comp[i]) {
c_id++;
bfs_comp(i, c_id);
}
}
// 2. Calculam limita secventei continue din aceeasi componenta conexa
for(int i = n; i >= 1; i--) {
if(i == n) {
R_block[i] = n;
} else if(global_comp[i] == global_comp[i+1]) {
R_block[i] = R_block[i+1];
} else {
R_block[i] = i;
}
}
// 3. Calculam pana unde bate fiecare nod IN INTERIORUL blocului curent
for(int i = 1; i <= n; i++) {
max_reach_node[i] = i;
for(int nxt : v[i]) {
// ne intereseaza muchiile doar daca nu depasesc limita blocului valid
if(nxt <= R_block[i]) {
max_reach_node[i] = max(max_reach_node[i], nxt);
}
}
}
vector<int> ans;
int st = 1;
while(st <= n) {
cnt = 0;
int poz = st;
int limit = R_block[st]; // Nu are rost sa cautam peste aceasta limita
// Golim coada de prioritati
while(!pq.empty()) pq.pop();
for(int i = st; i <= limit; i++) {
tata[i] = i;
dim[i] = 1;
cnt++;
comp_max_reach[i] = max_reach_node[i];
pq.push({comp_max_reach[i], i});
for(auto it : v[i]) {
if(it >= st && it < i) {
uneste(it, i);
}
}
if(cnt == 1) {
poz = i;
} else {
// Curatam pq de valorile vechi, inerte (Lazy Deletion)
while(!pq.empty()) {
int reach = pq.top().first;
int root = pq.top().second;
if(rad(root) != root || comp_max_reach[root] != reach) {
pq.pop();
} else {
break;
}
}
// CONDITIA MAGICA DE OPRIRE
// Daca componenta cu cel mai mic "reach" nu se mai poate lega
// de niciun nod viitor ramas (adica <= i), putem sa oprim cautarea.
if(!pq.empty() && pq.top().first <= i) {
break;
}
}
}
ans.push_back(poz - st + 1);
st = poz + 1; // Trecem la urmatorul interval
}
return ans;
}
