#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<vector<int> > graph;
vector<bool> vis1,vis2;
vector<int> ts,mi,res,size;
int t = 0;
int va,vb,vc;
int a,b,c;
int na = 0, nb = 0, nc = 0;
int n;
bool bol = false;
void dfs2(int u, int& mints);
void dfs3(int u);
int dfs(int u, int p){
if(vis1[u]) return 0;
if(ts[u]!=-1) return inf;
ts[u] = t++;
mi[u] = ts[u];
vis1[u] = true;
vector<int> cs;
int ma = 0;
for(int v : graph[u]) {
int s = dfs(v,u);
if(s!=inf){
size[u]+=s;
ma = max(ma,s);
}
if(v!=p) mi[u] = min(mi[u],mi[v]);
cs.push_back(s);
}
if(size[u]>=a && ma<a && !bol){
H(u);
H(size[u]);
H(ma);
P("a");
bol = true;
int p1 = size[u];
vector<int> startA;
for(int i = 0; i<graph[u].size(); i++){
H(cs[i]);
H(graph[u][i]);
H(mi[graph[u][i]]);
if(p1-cs[i]>=a&&mi[graph[u][i]]<ts[u]){
p1-=cs[i];
}
else if(ts[graph[u][i]] > ts[u]){
startA.push_back(graph[u][i]);
}
}
P(p1);
if(n-p1>=a){
if(p1>n-p1){
swap(a,b);
swap(va,vb);
}
na = 1;
vis2[u] = true;
res[u] = va;
for(int v : startA){
dfs2(v, ts[u]);
}
dfs3(0);
}
else{
res.assign(n,0);
}
}
vis1[u] = false;
return size[u];
}
void dfs2(int u, int& mints){
if(vis2[u] || ts[u] <mints || na >= a){
return;
}
vis2[u] = true;
res[u] = va;
na++;
for(int v : graph[u]){
dfs2(v, mints);
}
}
void dfs3(int u){
if(vis2[u] || nb>=b){
return;
}
vis2[u] = true;
res[u] = vb;
nb++;
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> aa[3] = {{A,1}, {B,2}, {C,3}};
sort(aa, aa+3);
va = aa[0].second; vb = aa[1].second; vc = aa[2].second;
a = aa[0].first; b = aa[1].first; c = aa[2].first;
n = N;
graph.resize(n);
vis1.resize(n,0);
vis2.resize(n,0);
ts.resize(n,-1);
mi.resize(n,inf);
res.resize(n,vc);
size.resize(n,1);
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);
H(bol);
return res;
}
