#include "boardgames.h"
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5+5;
int n, m;
vector<pair<int, int>> edges;
int banned = -1;
int par[MN], sz[MN];
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
}
void get_comps() {
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
for (auto [u, v]: edges) {
if (banned >= u) continue;
merge(u, v);
}
}
vector<int> partition_players(int N, int M, vector<int> X, vector<int> Y)
{
n = N;
m = M;
for (int i = 0; i < m; i++) {
edges.push_back({X[i], Y[i]});
}
sort(edges.begin(), edges.end());
get_comps();
vector<int> act;
for (int i = 1; i < n; i++) {
if (find(i) == find(i-1)) {
continue;
}
act.push_back(i - banned - 1);
banned = i-1;
get_comps();
}
act.push_back(n - banned - 1);
return act;
}
/*
int main()
{
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> X(M), Y(M);
for (int i = 0; i < M; i++)
{
assert(2 == scanf("%d %d", &X[i], &Y[i]));
}
fclose(stdin);
std::vector<int> K = partition_players(N, M, X, Y);
int g = static_cast<int>(K.size());
printf("%d\n", g);
for (int i = 0; i < g; i++)
{
printf(i == 0 ? "%d" : " %d", K[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
*/
