#include <bits/stdc++.h>
#include "split.h"
using namespace std;
///mt19937 rng((long long)(new char));
mt19937 rng(7777);
vector<int> solve(int n,vector<int> p, vector<int> q,int d1,int d2,double MAX_TIME){
time_t bg=clock();
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]);
}
bool done=0;
int need=0;
function<void(int, int,int)>place_to_all=[&](int a,int p,int value){
if(need==0) return;
assert(need>0);
sol[a]=value;
need--;
for(auto&b:g[a]){
if(b!=p&&sol[b]==0){
place_to_all(b,a,value);
}
}
};
function<void(int, int)>dfs=[&](int a,int p){
assert(0<=a&&a<n);
/// cout<<"a = "<<a<<" "<<p<<"\n";
if(done) return;
sub[a]=1;
for(auto&b:g[a]){
if(b!=p){
dfs(b,a);
if(done) return;
sub[a]+=sub[b];
}
}
if(done) return;
if(sub[a]>=d1&&n-sub[a]>=d2){
done=1;
need=d1;
place_to_all(a,p,1);
assert(need==0);
need=d2;
assert(p!=-1);
place_to_all(p,-1,2);
assert(need==0);
return;
}
if(sub[a]>=d2&&n-sub[a]>=d1){
done=1;
need=d2;
place_to_all(a,p,2);
assert(need==0);
need=d1;
assert(p!=-1);
place_to_all(p,-1,1);
assert(need==0);
return;
}
};
vector<int> t(n);
function<int(int)>get_root=[&](int a){
if(t[a]==a) return a;
return t[a]=get_root(t[a]);
};
while((double)(clock()-bg)/CLOCKS_PER_SEC<MAX_TIME){ /// redo so to calculate the time fewer times
int root=rng()%n;
shuffle(edges.begin(),edges.end(),rng);
for(int i=0;i<n;i++) g[i].clear(),t[i]=i;
int uni=0;
for(auto&it:edges){
if(get_root(it.first)!=get_root(it.second)){
uni++;
t[get_root(it.first)]=get_root(it.second);
g[it.first].push_back(it.second);
g[it.second].push_back(it.first);
}
}
assert(uni==n-1);
dfs(root,-1);
if(done){
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=0.5;
vector<int> dims={a, b, c};
for (int i=0;i<3;i++){
for(int j=i+1;j<3;j++){
auto sol=solve(n,p,q,dims[i],dims[j],TIME_EACH);
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);
}
