#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector<int> solve(int n,vector<int> p, vector<int> q,int d1,int d2){
assert(d1<=d2);
assert((int)p.size()==(int)q.size());
vector<pair<int, int>> edges((int)p.size());
for(int i=0;i<(int)p.size();i++) {
edges[i]={p[i], q[i]};
}
vector<int> sol(n,0);
vector<vector<int>> g(n);
vector<int> sub(n,0);
bool ok=1;
for(int i=0;i<(int)p.size();i++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
auto gi=g;
bool done=0;
int need=0;
vector<int> is_blo(n);
function<void(int, int)>place_to_all=[&](int a,int value){
assert(is_blo[a]==0);
if(need==0) return;
assert(need>0);
sol[a]=value;
need--;
for(auto&b:gi[a]){
if(is_blo[b]==1) continue;
if(sol[b]==0){
place_to_all(b,value);
}
}
};
vector<int> t(n);
function<int(int)>get_root=[&](int a){
if(t[a]==a) return a;
return t[a]=get_root(t[a]);
};
vector<vector<int>> back_edges(n);
vector<bool> vis(n);
vector<int> pr(n);
vector<int> dep(n,0);
vector<int> min_dep(n,0);
int vertex=-1;
vector<int> par_of(n);
function<void(int)>buildg=[&](int a){
min_dep[a]=dep[a];
assert(vis[a]==0);
vis[a]=1;
sub[a]=1;
vector<int> kd;
for(auto&b:g[a]){
if(vis[b]==0){
par_of[b]=a;
dep[b]=1+dep[a];
buildg(b);
sub[a]+=sub[b];
pr[b]=a;
kd.push_back(b);
min_dep[a]=min(min_dep[a],min_dep[b]);
}else{
if(dep[b]<dep[a]-1){
back_edges[a].push_back(b);
min_dep[a]=min(min_dep[a],dep[b]);
}
}
}
g[a]=kd;
if(sub[a]>=d1&&vertex==-1){
vertex=a;
}
};
for (auto&it:edges){
g[it.first].push_back(it.second);
g[it.second].push_back(it.first);
}
buildg(0);
assert(vertex!=-1);
int have=sub[vertex];
vector<int> yes,no;
for(auto &b:g[vertex]){
if(min_dep[b]<dep[vertex]&&have-sub[b]>=d1){
have-=sub[b];
no.push_back(b);
}else{
yes.push_back(b);
}
}
function<int()> getcnt=[&](){
int sol=0;
for(auto&x:is_blo)sol+=(x==0);
return sol;
};
function<void(int)>toggle_blo=[&](int a){
is_blo[a]^=1;
for(auto&b:g[a]) toggle_blo(b);
};
assert(par_of[vertex]!=-1);
assert((int)is_blo.size()==n);
if(have>=d1&&n-have>=d2){
need=d1;
for (int i=0;i<n;i++) is_blo[i]=1;
toggle_blo(vertex);
for(auto&v:no) toggle_blo(v);
place_to_all(vertex,1);
assert(getcnt()==have);
assert(need==0);
need=d2;
for(int i=0;i<n;i++) is_blo[i]=1;
toggle_blo(0);
toggle_blo(vertex);
for(auto&v:no) toggle_blo(v);
assert(getcnt()==n-have);
place_to_all(par_of[vertex],2);
assert(need==0);
return sol;
}
if(have>=d2&&n-have>=d1){
need=d2;
for (int i=0;i<n;i++) is_blo[i]=1;
toggle_blo(vertex);
for(auto&v:no) toggle_blo(v);
place_to_all(vertex,2);
assert(need==0);
need=d1;
for(int i=0;i<n;i++) is_blo[i]=1;
toggle_blo(0);
toggle_blo(vertex);
for(auto&v:no) toggle_blo(v);
place_to_all(par_of[vertex],1);
assert(need==0);
return sol;
}
return {};
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res;
double TIME_EACH=1.9;
vector<int> dims={a, b, c};
int mn1,mn2;
{
vector<int> aux=dims;
mn1=min_element(aux.begin(),aux.end())-aux.begin();
aux[mn1]=(int)1e9+7;
mn2=min_element(aux.begin(),aux.end())-aux.begin();;
}
for (int i=0;i<3;i++){
for(int j=0;j<3;j++){
bool is_ok=0;
is_ok|=((i==mn1&&j==mn2));
if(!is_ok) continue;
auto sol=solve(n,p,q,dims[i],dims[j]);
if(sol.empty()) continue;
int c1=0,c2=0;
for (auto &it:sol){
assert(it==0||it==1||it==2);
c1+=(it==1);
c2+=(it==2);
}
assert(c1==dims[i]);
assert(c2==dims[j]);
for (auto &it:sol){
if(it==0){
it=3-i-j;
}else{
if(it==1){
it=i;
}else{
assert(it==2);
it=j;
}
}
it++;
assert(1<=it&&it<=3);
}
return sol;
}
}
return vector<int>(n,0);
}
