#include "split.h"
#include <array>
#include <iostream>
#include <cassert>
using namespace std;
int n;
vector<int> lvl;
vector<vector<int>> adj;
vector<int> sz;
vector<int> low;
vector<int> par;
void dfs0(int x) {
sz[x]=1;
low[x]=lvl[x];
for(auto i:adj[x]) {
if(!sz[i]) {
lvl[i]=lvl[x]+1;
par[i]=x;
dfs0(i);
sz[x]+=sz[i];
low[x]=min(low[x], low[i]);
}else if(par[x]!=i) {
low[x]=min(low[x], lvl[i]);
}
}
}
vector<int> st;
vector<int> pars;
int best=0;
void fill_subtree(int x, int c, int& rem, vector<int>& res) {
if(!rem || res[x]) return ;
rem--;
res[x]=c;
for(auto i:adj[x]) {
if(par[x]!=i && !res[i]) {
fill_subtree(i, c, rem, res);
}
}
}
bool dfs1(int x, int a, int b, int id1, int id2, vector<int>& res) {
//~ cerr<<x<<" "<<a<<" "<<b<<"\n"<<flush;
st[x]=1;
if(par[x]!=-1) {
pars.push_back(par[x]);
while(best>=0 && (best>=(int)pars.size() || -sz[x]+sz[pars[best]]<a)) best--;
while(best+1<(int)pars.size() && -sz[x]+sz[pars[best+1]]>=a) best++;
if(best>=0 && best<(int)par.size() && sz[pars[best]]-sz[x]>=a) {
if(sz[x]>=b) {
fill_subtree(x, id2, b, res);
fill_subtree(pars[best], id1, a, res);
assert(b==0 && a==0);
return true;
}else if(low[x]<best && n-sz[pars[best]]+sz[x]>=b) {
fill_subtree(x, id2, b, res);
fill_subtree(pars[best], id1, a, res);
fill_subtree(pars[low[x]], id2, b, res);
assert(b==0 && a==0);
return true;
}
}
}
for(int i:adj[x]) {
if(!st[i]) {
if(dfs1(i, a, b, id1, id2, res)) return true;
}else if(par[x]!=i) {}
}
if(par[x]!=-1) {
pars.pop_back();
}
return false;
}
bool find_sol(int a, int b, int id1, int id2, vector<int>& res) {
pars.clear();
st.assign(n, 0);
best=0;
return dfs1(0, a, b, id1, id2, res);
}
vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q) {
n=n_;
adj.assign(n, vector<int>());
for(int i=0;i<(int)p.size();++i) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
sz.assign(n, 0);
lvl.assign(n, 0);
low.assign(n, n);
par.assign(n, -1);
dfs0(0);
vector<int> res(n, 0);
array<int, 3> x={a,b,c};
for(int i=0;i<3;++i) {
for(int j=0;j<3;++j) {
if(i!=j && find_sol(x[i], x[j], i+1, j+1, res)) {
for(auto& i:res) {
if(!i) i=1+2+3-(i+1)-(j+1);
assert(i==0 || i==1 || i==2 || i==3);
}
return res;
}
}
}
return res;
}
