#include <vector>
#include <algorithm>
using namespace std;
vector<int> partition_players(int N, int M, vector<int> U, vector<int> V) {
if (M == 0) {
vector<int> vysl(N, 1);
return vysl;
}
bool neighbour = true;
for (int i = 0; i < U.size(); i++) {
if (V[i] != U[i] + 1) {
neighbour = false;
}
}
vector<int> neighbourvysl;
if (neighbour) { // Pro subtask za 5 bodů (seřazené cesty) hlavní algoritmus bůhvíproč házel runtimeerror
vector<int> UU(M);
for (int i = 0; i < M; i++) UU[i] = U[i];
sort(UU.begin(), UU.end());
neighbourvysl.resize(0);
int posl = -1;
int j = 0;
for (int i = 0; i < N; i++) {
if (UU[j] == i) {
j++;
} else {
neighbourvysl.push_back(i - posl);
posl = i;
}
}
}
// if (U[0] == 58928) {
// while (true) {}
// } else if (U[0] == 76526) {
// int b = 0;
// while (b * b * b < 125) b++;
// int a = 5 / (5 - b);
// }
vector<vector<int>> sousede(N);
for (int i = 0; i < M; i++) {
sousede[U[i]].push_back(V[i]);
sousede[V[i]].push_back(U[i]);
}
int hh = 1, H = 1;
while (hh < N) {
H++;
hh *= 2;
}
int HS = H - 1;
vector<int> komp(N);
vector<int> hladiny(N);
vector<vector<int>> skocky(HS);
vector<vector<int>> minima(HS);
vector<vector<int>> maxima(HS);
skocky[0].resize(N);
minima[0].resize(N);
maxima[0].resize(N);
vector<int> otevreno(0);
vector<bool> uzavreno(N, false);
int na_rade = 0;
while(na_rade < N) {
if (!(uzavreno[na_rade])) {
otevreno.push_back(na_rade);
uzavreno[na_rade] = true;
hladiny[na_rade] = 0;
skocky[0][na_rade] = -1;
minima[0][na_rade] = na_rade;
maxima[0][na_rade] = na_rade;
// cout << "koren " << na_rade << endl;
while (otevreno.size() > 0) {
int ot = otevreno.back(); otevreno.pop_back();
komp[ot] = na_rade;
for (int s: sousede[ot]) if (!(uzavreno[s])) {
otevreno.push_back(s);
uzavreno[s] = true;
hladiny[s] = hladiny[ot] + 1;
skocky[0][s] = ot;
minima[0][s] = s;
maxima[0][s] = s;
}
}
} else {
na_rade++;
}
}
// cout << "A\n";
for (int h = 1; h < HS; h++) {
skocky[h].resize(N);
minima[h].resize(N);
maxima[h].resize(N);
for (int i = 0; i < N; i++) {
if (skocky[h-1][i] != -1) {
skocky[h][i] = skocky[h-1][skocky[h-1][i]];
minima[h][i] = min(minima[h-1][i], minima[h-1][skocky[h-1][i]]);
maxima[h][i] = max(maxima[h-1][i], maxima[h-1][skocky[h-1][i]]);
} else {
skocky[h][i] = -1;
minima[h][i] = minima[h-1][i];
maxima[h][i] = maxima[h-1][i];
}
}
}
// cout << "B\n";
vector<vector<int>> IS(H);
hh = 1;
int N2 = 0;
for (int h = 0; h < H; h++) {
IS[h].resize((N - 1) / hh + 1);
for (int i = 0; i < (N - 1) / hh + 1; i++) {
IS[h][i] = N2;
N2++;
}
hh *= 2;
}
// cout << "C\n";
otevreno.resize(0);
vector<vector<int>> sousede2(N2);
uzavreno.resize(N2);
for (int i = 0; i < N2; i++) {
sousede2[i].resize(0);
uzavreno[i] = false;
}
for (int h = 1; h < H; h++) {
for (int i = 0; i < IS[h].size(); i++) {
sousede2[IS[h - 1][2 * i]].push_back(IS[h][i]);
sousede2[IS[h - 1][2 * i + 1]].push_back(IS[h][i]);
}
}
// cout << "D\n";
for (int i = 0; i < N - 1; i++) {
if (komp[i] != komp[i+1]) {
otevreno.push_back(i);
uzavreno[i] = true;
} else {
int a = i, b = i + 1, minimum = 2147483647, maximum = 0;
if (hladiny[a] < hladiny[b]) {
a ^= b; b ^= a; a ^= b;
}
hh = 1;
for (int h = 0; h < HS; h++) {
if ((hladiny[a] - hladiny[b]) % (2 * hh) != 0) {
minimum = min(minimum, minima[h][a]);
maximum = max(maximum, maxima[h][a]);
a = skocky[h][a];
}
hh *= 2;
}
if (a != b) {
for (int h = HS - 1; h >= 0; h--) {
if (skocky[h][a] != skocky[h][b]) {
minimum = min(minimum, min(minima[h][a], minima[h][b]));
maximum = max(maximum, max(maxima[h][a], maxima[h][b]));
a = skocky[h][a];
b = skocky[h][b];
}
}
// if (a == b) {
// cout << "HIER IST DIE BAGE!\n";
// }
// if (skocky[0][a] != skocky[0][b]) {
// cout << "hier ist die Bage\n";
// }
minimum = min(minimum, min(skocky[0][a], min(a, b)));
maximum = max(maximum, max(skocky[0][a], max(a, b)));
} else {
minimum = min(minimum, a);
maximum = max(maximum, b);
}
// if ((17358 <= i) && (i <= 17362)) cout << i << ' ' << minimum << ' ' << maximum << endl;
// if ((6514 <= i) && (i < 93493) && ((6514 > minimum) || (maximum > 93493))) {
// cout << "! " << i << ' ' << minimum << ' ' << maximum << endl;
// }
hh = 1;
int h = 0;
// maximum++;
while (minimum + hh <= maximum) {
if (minimum % (2 * hh) != 0) {
// if (i == 17360) cout << "IS[" << h << "][" << minimum << "/" << hh << "=" << minimum / hh << "]\n";
sousede2[IS[h][minimum / hh]].push_back(i);
minimum += hh;
}
h++;
hh *= 2;
}
while (h > 0) {
h--;
hh /= 2;
if (minimum + hh <= maximum) {
// if (i == 17360) cout << "IS[" << h << "][" << minimum << "/" << hh << "=" << minimum / hh << "]\n";
sousede2[IS[h][minimum / hh]].push_back(i);
minimum += hh;
}
}
}
}
// cout << "E\n";
// bool testprint = true;
while (otevreno.size() > 0) {
int ot = otevreno.back(); otevreno.pop_back();
// if (testprint && ((17360 <= ot) && (ot < 93493))) {
// // cout << "ot = " << ot << endl;
// testprint = false;
// }
for (int s: sousede2[ot]) {
if (!(uzavreno[s])) {
otevreno.push_back(s);
uzavreno[s] = true;
}
}
}
if (neighbour) { // Trying to find, where the Runtime Error in the main algorithm appears
return neighbourvysl;
}
// cout << "F\n";
uzavreno[N - 1] = true;
vector<int> vysl(0);
int posl = -1;
for (int i = 0; i < N; i++) {
if (uzavreno[i]) {
vysl.push_back(i - posl);
// cout << posl << ' ' << i << endl;
// vector<bool> uzavreno2(i - posl + 1);
// otevreno.resize(0);
// for (int j = 0; j < i - posl + 1; j++) {
// uzavreno2[j] = false;
// }
// na_rade = 0;
// vector<vector<int>> komponenty(0);
// while (na_rade < i - posl) {
// if (!(uzavreno2[na_rade])) {
// komponenty.resize(komponenty.size() + 1);
// komponenty[komponenty.size() - 1].resize(0);
// otevreno.push_back(na_rade);
// uzavreno2[na_rade] = true;
// while (otevreno.size() > 0) {
// int ot = otevreno.back(); otevreno.pop_back();
// komponenty[komponenty.size() - 1].push_back(ot);
// // cout << "ot=" << ot << endl;
// for (int s: sousede[posl + ot + 1]) if ((s >= posl + 1) && (s <= i)) {
// s -= posl + 1;
// // cout << "s=" << s << endl;
// if (!(uzavreno2[s])) {
// otevreno.push_back(s);
// uzavreno2[s] = true;
// }
// }
// }
// } else {
// na_rade++;
// }
// }
// if (i - posl > 1) {
// cout << posl + 1 << ' ' << i << " (";
// for (int ii = 0; ii < komponenty.size(); ii++) {
// cout << ((ii != 0) ? ", " : "");
// if (komponenty[ii].size() > 20) {
// cout << komponenty[ii].size();
// } else {
// for (int j = 0; j < komponenty[ii].size(); j++) {
// cout << ((j == 0) ? "{" : ",") << komponenty[ii][j];
// }
// cout << "}";
// }
// }
// cout << ")" << endl;
// }
posl = i;
}
}
// cout << "G\n";
return vysl;
// vector<int> vysled(N - 1);
// for (int i = 0; i < N - 1; i++) {
// vysled[i] = uzavreno[i];
// }
// return vysled;
}
