#include "split.h"
using namespace std;
using ll=long long;
#include <bits/stdc++.h>
int maxn=1e5;
vector<int> s;
vector<int> vis(maxn,0);
vector<vector<int>> adj(maxn);
int cnt=0, now=1;
int n,a,b,c;
void dfs(int u) {
if (vis[u]) return;
vis[u]=1;
cnt++;
if (now==1) {
if (cnt<=a) s[u]=1;
else {
cnt=1; now=2;
}
}
if (now==2) {
if (cnt<=b) s[u]=2;
else {
cnt=1; now=3;
}
}
if (now==3) {
if (cnt<=c) s[u]=3;
else {
cnt=1; now=4;
}
}
for (auto v:adj[u]) {
dfs(v);
}
}
struct DSU {
vector<int> p;
vector<int> r;
vector<int> sz;
DSU(int n) {
p.assign(n,0);
r.assign(n,0);
sz.assign(n,1);
for (int i=0; i<n; ++i) p[i]=i;
}
int get(int i) {
return p[i]==i ? i : get(p[i]);
}
int getsz(int i) {
i=get(i);
return sz[i];
}
void uni(int a, int b) {
a=get(a);
b=get(b);
if (a==b) return;
if (r[a]==r[b]) r[a]++;
if (r[a]>r[b]) {
p[b]=a;
sz[a]+=sz[b];
} else {
p[a]=b;
sz[b]+=sz[a];
}
}
};
vector<int> par(1e5,-1);
void _dfs(vector<int>&c, int v) {
if (vis[v]) return;
vis[v]=1;
for (auto u:adj[v]) {
if (!vis[u]) par[u]=v;
if (u==par[v]) continue;
_dfs(c,u);
c[v]+=c[u];
}
//cout<<v<<' '<<c[v]<<'\n';
}
int findcentroid(vector<int>&c, int v) {
for (auto u:adj[v]) {
if (u==par[v]) continue;
if (c[u]>n/2) return findcentroid(c,u);
}
return v;
}
vector<int> _p3() {
int _b, _a;
vector<int> tmp={a,b,c}; sort(tmp.begin(), tmp.end());
_b=tmp[1]; _a=tmp[0];
s.assign(n,0);
vector<int> ch(n,1);
_dfs(ch,0);
int cent=findcentroid(ch,0);
ch.assign(n,1);
vis.assign(n,0);
par.assign(n,-1);
_dfs(ch,cent);
int ind=adj[cent][0];
for (auto v:adj[cent]) if (ch[ind]<ch[v]) ind=v;
int mx=ch[ind];
if (mx<=_a) return s;
int A,B,C;
if (a<b) {
if (a<c) A=1;
else A=3;
if (b<c) { B=2; C=(A+2)%4; }
else { B=(A+2)%4; C=2; }
} else {
if (b<c) A=2;
else A=3;
if (a<c) { B=1; C=A+1-2*(A%2); }
else { B=A+1-2*(A%2); C=1; }
}
vis.assign(n,0);
s.assign(n,C);
int cnt=0;
queue<int> q; q.push(ind); vis[cent]=1; vis[ind]=1;
while (cnt<_a) {
int u=q.front(); q.pop();
s[u]=A;
for (auto v:adj[u]) {
if (!vis[v]) {
vis[v]=1;
q.push(v);
}
}
++cnt;
}
while (q.size()) q.pop();
q.push(cent); cnt=0;
while (cnt<_b) {
int u=q.front(); q.pop();
s[u]=B;
for (auto v:adj[u]) {
if (!vis[v]) {
vis[v]=1;
q.push(v);
}
}
++cnt;
}
return s;
}
vector<int> find_split(int N, int A, int B, int C, vector<int>p, vector<int> q) {
int m=p.size();
n=N, a=A, b=B, c=C;
s.assign(n,0);
for (int i=0; i<m; ++i) {
int u=p[i], v=q[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
if (m==n-1) return _p3();
int foo=1, start=0;
for (int i=0; i<n; ++i) {
foo&=adj[i].size()<=2;
if (adj[i].size()==1) start=i;
}
if (foo) {
dfs(start);
return s;
}
if (a==1) {
s.assign(n,3);
queue<int> q; q.push(0); vis[0]=1;
int cnt=0;
while (cnt<b) {
int u=q.front(); q.pop();
s[u]=2;
cnt++;
for (auto v:adj[u]) {
if (!vis[v]) {
vis[v]=1;
q.push(v);
}
}
}
for (int i=0; i<n; ++i) if (s[i]==3) {s[i]=1; break;}
return s;
}
return vector<int>(n,0);
}
