#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define sz(x) (int)(x).size()
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 1e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<int> leg[nmax];
struct Tree {
vector<int> g[nmax];
int root;
void clear() {
for(int i = 0; i < n; i++)
g[i].clear();
return;
}
void addedge(int a, int b) {
g[a].emplace_back(b);
g[b].emplace_back(a);
}
vector<int> togive;
int mxarea[nmax], area[nmax], p[nmax];
void down(int node, int f) {
p[node] = f;
for(auto x : g[node]) {
if(x == f) continue;
down(x, node);
area[node] += area[x];
mxarea[node] = max(mxarea[node], area[x]);
}
area[node]++;
}
void init() { togive.resize(n, 0); down(root, root); }
void fillgreedy(int node, int f, int& a) {
if(a == 0) return;
sort(all(g[node]), [&](int x, int b) { return area[x] < area[b] || (area[x] > a && area[b] > a && mxarea[x] < mxarea[b]); });
togive[node] = 1;
a--;
for(auto x : g[node]) {
if(x == f) continue;
fillgreedy(x, node, a);
if(a == 0) return;
}
}
vector<int> getbydown(int a) {
std::fill(all(togive), 0);
int best = root;
for(int i = 0; i < n; i++)
if(area[i] >= a && area[best] > area[i]) best = i;
fillgreedy(best, p[best], a);
return togive;
}
vector<int> getbyroot(int a) {
std::fill(all(togive), 0);
fillgreedy(root, root, a);
return togive;
}
int flag = 2;
int fill(int node, vector<int>& occ, int& b) {
if(b == 0) return 0;
if(occ[node] != 0) return 0;
occ[node] = flag;
int sum = 1;
b--;
for(auto x : leg[node])
sum += fill(x, occ, b);
return sum;
}
void fill(vector<int> &occ, int b) {
for(int i = 0; i < n; i++) {
if(occ[i] == 0) {
flag++;
int tmp = b;
fill(i, occ, b);
if(b == 0) {
//for(auto x : occ)
//cerr << x << ' ';
//cerr << '\n';
//cerr << flag << '\n';
for(auto &x : occ) {
if(x == 1) continue;
if(x == flag) x = 2;
else x = 3;
}
return;
}
b = tmp;
}
}
occ.back() = -1;
return;
}
} tree;
int occ[nmax];
void dfs(int node) {
if(occ[node] == 1) return;
occ[node] = 1;
for(auto x : leg[node]) {
if(occ[x] == 0) {
tree.addedge(node, x);
dfs(x);
}
}
return;
}
void constr_tree(vector<pii>& edg, int rt) {
tree.clear();
for(int i = 0; i < n; i++)
leg[i].clear();
for(auto [a, b] : edg)
leg[a].emplace_back(b),
leg[b].emplace_back(a);
tree.root = rt;
dfs(rt);
tree.init();
}
int rnd(int x) {return rng() % x;}
vector<int> sol;
void verif(int node, int col) {
sol[node] = -1;
for(auto x : leg[node]) {
if(sol[x] == col) {
verif(x, col);
}
}
}
std::vector<int> find_split(int N, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
n = N;
int hsh[3] = {0, 1, 2};
{ // renumerotare
if(a > b)
swap(hsh[0], hsh[1]),
swap(a, b);
if(b > c)
swap(hsh[1], hsh[2]),
swap(b, c);
if(a > b)
swap(hsh[0], hsh[1]),
swap(a, b);
}
vector<pii> edg;
for(int i = 0; i < sz(p); i++)
edg.emplace_back(p[i], q[i]);
vector<int> var(n, -1);
int counted = 0;
int sus = 0;
do {
constr_tree(edg, sus);
vector<int> var1 = tree.getbydown(a), var2 = tree.getbyroot(a);
tree.fill(var1, b);
tree.fill(var2, b);
if(var1.back() == -1)
swap(var1, var2);
var = move(var1);
counted++;
random_shuffle(all(edg), rnd);
//sus = rnd(n);
} while(var.back() == -1 && counted < 1);
if(var.back() == -1) {
fill(all(var), 0);
return var;
}
sol = var;
int cnts = 0;
for(int i = 0; i < n; i++) {
if(sol[i] == 1)
cnts++,
verif(i, 1);
if(sol[i] == 2)
cnts++,
verif(i, 2);
}
//cerr << cnts << '\n';
assert(cnts == 2);
int cnt[3] = {0, 0, 0};
for(auto &x : var) {
x--;
x = hsh[x];
x++;
}
return var;
}
