#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000
#define mod 1000000007
std::vector<int> partition_players(int n, int m, std::vector<int> X, std::vector<int> Y){
vvi edges(n);
for(int i = 0; i < m; i++){
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
for(int i = 0; i < n; i++){
sort(edges[i].begin(), edges[i].end());
}
vi dp(n + 1, inf);
dp.back() = 0;
vi next(n, -1);
dp[n - 1] = 1;
next[n - 1] = n;
for(int i = n - 2; i >= 0; i--){
ll cnt = 0;
priority_queue<ll> q;
q.push(-i);
ll mx = -1;
ll discovered = 0;
vi was(n, 0);
while(!q.empty()){
ll u = -q.top();
q.pop();
mx = max(mx, u);
was[u] = 1;
discovered++;
cnt++;
if(n > 2000 && m > 4000 && cnt > 2){
break;
}
if(discovered == mx - i + 1){
if(dp[i] > dp[mx + 1] + 1){
dp[i] = min(dp[i], dp[mx + 1] + 1);
next[i] = mx + 1;
}
}
for(int j = 0; j < edges[u].size(); j++){
ll v = edges[u][j];
if(v < i) continue;
if(was[v]) continue;
q.push(-v);
was[v] = true;
}
}
}
vector<int> ans;
ll akt = 0;
while(akt < n){
ans.push_back(next[akt] - akt);
akt = next[akt];
}
return ans;
}
