#include "split.h"
#include <bits/stdc++.h>
#define P(a) do{if(debug)cout<<a<<endl;} while(false);
#define H(a) P(#a<<": "<<a);
using namespace std;
const int inf = 2e9;
const bool debug = 0;
vector<int> ts, mi, size;
vector<bool> open;
vector<int> res;
vector<vector<int> > graph;
int a,b,c,n,va,vb,vc;
int na = 0, nb = 0;
int t = 0;
bool bol = false;
vector<bool> vis;
void dfs2(int u, int& mints);
void dfs3(int u);
int dfs(int u, int p){
if(open[u]){
return 0;
}
int ms = 0;
ts[u] = t++;
mi[u] = ts[u];
open[u] = true;
vector<int> realchildren;
for(int i = 0; i<graph[u].size(); i++) { int v = graph[u][i]; if(v!=p){
if(!open[v]) realchildren.push_back(i);
int s = dfs(v,u);
size[u]+=s;
ms = max(ms,s);
mi[u] = min(mi[u], mi[v]);
} else {
realchildren.push_back(i);
}
}
if(size[u]>=a&&ms<a&&!bol){
H(u);
int p1 = size[u];
H(p1);
vector<bool> startA(graph[u].size(),1);
for(int i = 0; i<graph[u].size(); i++) {
int v = graph[u][i];
if(mi[v]<ts[u] && (p1-size[v]>=a||ts[v]<ts[u])){
H(v);
p1-=size[v];
startA[i] = false;
}
}
if(n-p1>=a){
if(p1>n-p1){
swap(va,vb);
swap(a,b);
}
//YES
//A: dfs starting from children with startA[v] == true, over nodes with ts>ts[u]
//B: then dfs starting from p, ignoring nodes that already have been chosen
//C: default option
res[u] = va;
vis[u] = true;
na = 1;
for(int i = 0; i<graph[u].size();i++) if(startA[i]){
dfs2(graph[u][i],ts[u]);
}
for(int i = 0; i<graph[u].size();i++) if(!startA[i]){
dfs3(graph[u][i]);
}
}
else{
//NO
//res = {0,0,0,...}
res.assign(n,0);
}
bol = true;
}
return size[u];
}
void dfs2(int u, int& mints){
if(vis[u]||ts[u]<=mints||na>=a){
return;
}
res[u] = va;
na++;
vis[u] = true;
for(int v : graph[u]) {
dfs2(v,mints);
}
}
void dfs3(int u){
if(vis[u]||nb>=b){
return;
}
res[u] = vb;
nb++;
vis[u] = true;
for(int v : graph[u]){
dfs3(v);
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
pair<int,int> d[3] = {{A,1},{B,2},{C,3}};
n = N;
sort(d, d+3);
a = d[0].first; b = d[1].first; c = d[2].first;
va = d[0].second; vb = d[1].second; vc = d[2].second;
graph.resize(n);
ts.resize(n,-1);
mi.resize(n,inf);
size.resize(n,1);
vis.resize(n,false);
open.resize(n, false);
res.resize(n,vc);
for(int i = 0; i<p.size();i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
dfs(0,0);
return res;
}
