#include<bits/stdc++.h>
#include "split.h"
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using ll = long long;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t))cerr<<", ";
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
const int N=1e5+5;
vi E[N], E2[N];
vi kto[N];
int pre[N], lo[N], par[N], czy_art[N], czy_root[N], bcc[N], roz[N], siz[N];
int n;
int cent;
int wsk=1;
void dfs(int v){
lo[v]=pre[v]=wsk++;
for(int u:E[v]){
if(!pre[u]){
par[u]=v;
dfs(u);
lo[v]=min(lo[v], lo[u]);
}
else if(u!=par[v]){
lo[v]=min(lo[v], pre[u]);
}
}
if(par[v]!=-1 && lo[v]>=pre[par[v]]){
//deb(v, par[v]);
czy_art[par[v]]=1;
}
}
void color(int v, int c){
if(v==c)czy_root[v]=1;
bcc[v]=c;
roz[c]++;
kto[c].pb(v);
for(int u:E[v]){
if(v==par[u]){
if(!czy_art[u] && !czy_art[v])color(u, c);
else color(u, u);
}
}
}
void dfs_cent(int v){
siz[v]=roz[v];
bool czy=1;
for(int u:E2[v]){
if(!siz[u]){
dfs_cent(u);
siz[v]+=siz[u];
if(2*siz[u]>n)czy=0;
}
}
if(czy && 2*(n-siz[v])<=n){
cent=v;
}
}
void dfs_sz(int v){
siz[v]=roz[v];
pre[v]=1;
for(int u:E2[v]){
if(!pre[u]){
par[u]=v;
dfs_sz(u);
siz[v]+=siz[u];
}
}
}
vi find(int a, vi dozw){
//deb(a, dozw[0], dozw[1], dozw[2]);
vi V;
for(int i=0; i<n; i++){
if(dozw[i]){
dozw[i]=0;
V.pb(i);
break;
}
}
for(int i=0; i<V.size(); i++){
int v=V[i];
//deb(v);
for(int u:E[v]){
if(dozw[u]){
dozw[u]=0;
V.pb(u);
}
}
}
for(int i=0; i<n; i++){
if(dozw[i])assert(false);
}
//if(V.size()<a)return V;
//assert(V.size()>=a);
V.resize(a);
return V;
}
vi get_subtree(int u){
vi uzy(n);
vi V;
V.pb(u);
uzy[u]=1;
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int uu:E2[v]){
if(par[uu]==v){
uzy[uu]=1;
V.pb(uu);
}
}
}
int t=V.size();
for(int i=0; i<t; i++){
int v=V[i];
for(int uu:kto[v]){
//deb(uu);
if(!uzy[uu]){
V.pb(uu);
uzy[uu]=1;
}
}
}
return V;
}
void dfs2(int v){
lo[v]=pre[v]=wsk++;
for(int u:E2[v]){
if(!pre[u]){
par[u]=v;
dfs2(u);
lo[v]=min(lo[v], lo[u]);
}
else if(u!=par[v]){
lo[v]=min(lo[v], pre[u]);
}
}
if(par[v]!=-1 && lo[v]>=pre[par[v]]){
czy_art[par[v]]=1;
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> uu, vector<int> vv) {
n=_n;
for(int i=0; i<uu.size(); i++){
E[uu[i]].pb(vv[i]);
E[vv[i]].pb(uu[i]);
}
par[0]=-1;
dfs(0);
int ile=0;
for(int u:E[0]){
if(par[u]==0)ile++;
}
czy_art[0]=(ile!=1);
for(int i=0; i<n; i++){
//deb(i, par[i], czy_art[i]);
}
color(0, 0);
for(int i=0; i<n; i++){
pre[i]=0;
for(int j:E[i]){
if(bcc[i]!=bcc[j])E2[bcc[i]].pb(bcc[j]);
}
//deb(i, bcc[i]);
}
for(int i=0; i<n; i++){
if(!czy_root[i])continue;
sort(all(E2[i]));
E2[i].resize(unique(all(E2[i]))-E2[i].begin());
//deb(i, E2[i].size());
for(int u:E2[i]){
//deb(u);
}
}
cent=-5;
dfs_cent(0);
par[cent]=-1;
dfs_sz(cent);
deb(cent);
for(int i=0; i<n; i++){
if(czy_root[i]){
//deb(i, roz[i], siz[i])
}
}
int A=min({a, b, c}), C=max({a, b, c});
int B=n-A-C;
bool bb=0;
vector<int> res(n, 0);
vi X,Y,Z;
for(int u:E2[cent]){
if(siz[u]>=A){
assert(n-siz[u]>=B);
deb(u, siz[u], A);
vi V=get_subtree(u);
//assert(n<=5000);
vi dozw(n);
for(int i:V){
dozw[i]=1;
}
X=find(A, dozw);
//assert(X.size()==A);
for(int i:X){
//deb(i);
}
for(int &i:dozw)i^=1;
Y=find(B, dozw);
//assert(Y.size()==B);
for(int &i:dozw)i=0;
for(int i:Y){
dozw[i]=1;
}
for(int i:X){
dozw[i]=1;
}
for(int i=0; i<n; i++){
if(!dozw[i])Z.pb(i);
}
bb=1;
break;
}
}
deb("a");
if(!bb){
if(roz[0]==1)return res;
//if(n>=5000)assert(false);
/*for(int u:E2[cent]){
roz[u]=siz[u];
czy_root[u]=1;
kto[u]=get_subtree(u);
assert(siz[u]==kto[u].size());
roz[u]=siz[u];
for(int v:kto[u])bcc[v]=u, czy_root[v]=0;
}
for(int u:kto[0]){
if(u!=0){
kto[u]={u};
bcc[u]=u;
roz[u]=1;
czy_root[u]=1;
}
}
kto[0]={0};
roz[0]=1;
for(int i=0; i<n; i++)E2[i].clear();
for(int i=0; i<n; i++){
pre[i]=0;
for(int j:E[i]){
if(bcc[i]!=bcc[j])E2[bcc[i]].pb(bcc[j]);
}
//deb(i, bcc[i]);
}
for(int i=0; i<n; i++){
if(!czy_root[i])continue;
sort(all(E2[i]));
E2[i].resize(unique(all(E2[i]))-E2[i].begin());
}
for(int i=0; i<n; i++){
//deb(i, bcc[i], czy_root[i], kto[i].size(), E2[i].size())
if(czy_root[i]){
for(int u:E2[i]){
//deb(u);
}
}
}
vi V;
for(int i=0; i<n; i++){
if(czy_root[i])V.pb(i);
}
vi czy_cand(V.size(), 1);
vi mamy;
vi cand;
int sum=0;
cand.pb(0);
czy_cand[0]=0;
//assert(A==1);
while(sum<A){
for(int i:V)pre[i]=0, czy_art[i]=0;
for(int i:mamy)pre[i]=1e9;
wsk=1;
bb=0;
for(int i:V){
if(!pre[i]){
par[i]=-1;
dfs2(i);
bb=1;
break;
}
}
assert(bb);
bb=0;
ile=0;
for(int u:E[0]){
if(par[u]==0)ile++;
}
czy_art[0]=(ile!=1);
for(int &i:cand){
if(1){
mamy.pb(i);
sum+=roz[i];
for(int u:E2[i]){
if(czy_cand[u]){
czy_cand[u]=0;
cand.pb(u);
}
}
bb=1;
swap(i, cand.back());
cand.pp();
break;
}
}
assert(bb);
}*/
//assert(mamy.size()==1);
vi dozw(n);
/*for(int i:mamy){
for(int j:kto[i]){
dozw[j]=1;
}
}*/
dozw[0]=1;
X={0};
//X=find(A, dozw);
for(int i:X){
//deb(i);
}
for(int &i:dozw)i^=1;
Y=find(B, dozw);
for(int &i:dozw)i=0;
for(int i:Y){
dozw[i]=1;
}
for(int i:X){
dozw[i]=1;
}
for(int i=0; i<n; i++){
if(!dozw[i])Z.pb(i);
}
}
if(A!=a){
swap(A, B);
swap(X, Y);
}
if(A!=a){
swap(A, C);
swap(X, Z);
}
if(B!=b){
swap(C, B);
swap(Z, Y);
}
for(int i:X)res[i]=1;
for(int i:Y)res[i]=2;
for(int i:Z)res[i]=3;
return res;
}
