#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.at(i) != U.at(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.at(i) = U.at(i);
// // sort(UU.begin(), UU.end());
// neighbourvysl.resize(0);
// int posl = -1;
// int j = 0;
// for (int i = 0; i < N; i++) {
// if (UU.at(j) == i) {
// j++;
// } else {
// neighbourvysl.push_back(i - posl);
// posl = i;
// }
// }
// }
// if (U.at(0) == 58928) {
// while (true) {}
// } else if (U.at(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.at(U.at(i)).push_back(V.at(i));
sousede.at(V.at(i)).push_back(U.at(i));
}
int hh = 1, H = 0;
while (hh <= N) {
H++;
hh *= 2;
}
int HS = H - 0;
vector<int> komp(N);
vector<int> hladiny(N);
vector<vector<int>> skocky(HS);
vector<vector<int>> minima(HS);
vector<vector<int>> maxima(HS);
skocky.at(0).resize(N);
minima.at(0).resize(N);
maxima.at(0).resize(N);
vector<int> otevreno(0);
vector<bool> uzavreno(N, false);
int na_rade = 0;
while(na_rade < N) {
if (!(uzavreno.at(na_rade))) {
otevreno.push_back(na_rade);
uzavreno.at(na_rade) = true;
hladiny.at(na_rade) = 0;
skocky.at(0).at(na_rade) = -1;
minima.at(0).at(na_rade) = na_rade;
maxima.at(0).at(na_rade) = na_rade;
// cout << "koren " << na_rade << endl;
while (otevreno.size() > 0) {
int ot = otevreno.back(); otevreno.pop_back();
komp.at(ot) = na_rade;
for (int s: sousede.at(ot)) if (!(uzavreno.at(s))) {
otevreno.push_back(s);
uzavreno.at(s) = true;
hladiny.at(s) = hladiny.at(ot) + 1;
skocky.at(0).at(s) = ot;
minima.at(0).at(s) = s;
maxima.at(0).at(s) = s;
}
}
} else {
na_rade++;
}
}
// cout << "A\n";
for (int h = 1; h < HS; h++) {
skocky.at(h).resize(N);
minima.at(h).resize(N);
maxima.at(h).resize(N);
for (int i = 0; i < N; i++) {
if (skocky.at(h-1).at(i) != -1) {
skocky.at(h).at(i) = skocky.at(h-1).at(skocky.at(h-1).at(i));
minima.at(h).at(i) = min(minima.at(h-1).at(i), minima.at(h-1).at(skocky.at(h-1).at(i)));
maxima.at(h).at(i) = max(maxima.at(h-1).at(i), maxima.at(h-1).at(skocky.at(h-1).at(i)));
} else {
skocky.at(h).at(i) = -1;
minima.at(h).at(i) = minima.at(h-1).at(i);
maxima.at(h).at(i) = maxima.at(h-1).at(i);
}
}
}
// cout << "B\n";
vector<vector<int>> IS(H);
hh = 1;
int N2 = 0;
for (int h = 0; h < H; h++) {
IS.at(h).resize((N - hh) / hh + 1);
for (int i = 0; i < (N - hh) / hh + 1; i++) {
IS.at(h).at(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.at(i).resize(0);
uzavreno.at(i) = false;
}
for (int h = 1; h < H; h++) {
for (int i = 0; i < IS.at(h).size(); i++) {
sousede2.at(IS.at(h - 1).at(2 * i)).push_back(IS.at(h).at(i));
if (2 * i + 1 < IS.at(h - 1).size()) sousede2.at(IS.at(h - 1).at(2 * i + 1)).push_back(IS.at(h).at(i));
}
}
// cout << "D\n";
for (int i = 0; i < N - 1; i++) {
if (komp.at(i) != komp.at(i+1)) {
otevreno.push_back(i);
uzavreno.at(i) = true;
} else {
int a = i, b = i + 1, minimum = 2147483647, maximum = 0;
if (hladiny.at(a) < hladiny.at(b)) {
a ^= b; b ^= a; a ^= b;
}
hh = 1;
for (int h = 0; h < HS; h++) {
if ((hladiny.at(a) - hladiny.at(b)) % (2 * hh) != 0) {
minimum = min(minimum, minima.at(h).at(a));
maximum = max(maximum, maxima.at(h).at(a));
a = skocky.at(h).at(a);
}
hh *= 2;
}
if (a != b) {
for (int h = HS - 1; h >= 0; h--) {
if (skocky.at(h).at(a) != skocky.at(h).at(b)) {
minimum = min(minimum, min(minima.at(h).at(a), minima.at(h).at(b)));
maximum = max(maximum, max(maxima.at(h).at(a), maxima.at(h).at(b)));
a = skocky.at(h).at(a);
b = skocky.at(h).at(b);
}
}
// if (a == b) {
// cout << "HIER IST DIE BAGE!\n";
// }
// if (skocky.at(0).at(a) != skocky.at(0).at(b)) {
// cout << "hier ist die Bage\n";
// }
minimum = min(minimum, min(skocky.at(0).at(a), min(a, b)));
maximum = max(maximum, max(skocky.at(0).at(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.at(" << h << ").at(" << minimum << "/" << hh << "=" << minimum / hh << ")\n";
sousede2.at(IS.at(h).at(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.at(" << h << ").at(" << minimum << "/" << hh << "=" << minimum / hh << ")\n";
sousede2.at(IS.at(h).at(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.at(ot)) {
if (!(uzavreno.at(s))) {
otevreno.push_back(s);
uzavreno.at(s) = true;
}
}
}
// cout << "F\n";
uzavreno.at(N - 1) = true;
vector<int> vysl(0);
int posl = -1;
for (int i = 0; i < N; i++) {
if (uzavreno.at(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.at(j) = false;
// }
// na_rade = 0;
// vector<vector<int>> komponenty(0);
// while (na_rade < i - posl) {
// if (!(uzavreno2.at(na_rade))) {
// komponenty.resize(komponenty.size() + 1);
// komponenty.at(komponenty.size() - 1).resize(0);
// otevreno.push_back(na_rade);
// uzavreno2.at(na_rade) = true;
// while (otevreno.size() > 0) {
// int ot = otevreno.back(); otevreno.pop_back();
// komponenty.at(komponenty.size() - 1).push_back(ot);
// // cout << "ot=" << ot << endl;
// for (int s: sousede.at(posl + ot + 1)) if ((s >= posl + 1) && (s <= i)) {
// s -= posl + 1;
// // cout << "s=" << s << endl;
// if (!(uzavreno2.at(s))) {
// otevreno.push_back(s);
// uzavreno2.at(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.at(ii).size() > 20) {
// cout << komponenty.at(ii).size();
// } else {
// for (int j = 0; j < komponenty.at(ii).size(); j++) {
// cout << ((j == 0) ? "{" : ",") << komponenty.at(ii).at(j);
// }
// cout << "}";
// }
// }
// cout << ")" << endl;
// }
posl = i;
}
}
// cout << "G\n";
// cout << neighbourvysl.size() << ' ' << vysl.size() << endl;
// if (neighbour) { // Trying to find, where the Runtime Error in the main algorithm appears
// return neighbourvysl;
// }
return vysl;
// vector<int> vysled(N - 1);
// for (int i = 0; i < N - 1; i++) {
// vysled.at(i) = uzavreno.at(i);
// }
// return vysled;
}
