#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) x.begin(),x.end()
#define pii pair<int, int>
#define f first
#define s second
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = ", _do(__VA_ARGS__)
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
const int maxn = 1e5+5;
vector<int> g[maxn];
vector<int> ret;
vector<int> Cols = {1,2,3};
int sz[maxn];
int pa[maxn];
bool seen[maxn];
int A, B;
void dfs(int v, int p = -1) {
sz[v] = 1;
pa[v] = p;
seen[v] = 1;
for (int u : g[v]) {
if (u!=p && !seen[u]) {
dfs(u,v);
sz[v] += sz[u];
}
}
}
void dc(int v, int p, int c) {
if (c == Cols[1] && B==0) return;
if (c == Cols[0] && A==0) return;
ret[v] = c;
if (c == Cols[1]) {
--B;
}
if (c == Cols[0]) {
--A;
}
for (int u : g[v]) {
if (u!=p && ret[u]==0) {
dc(u,v,c);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size();
for (int i = 0; i<m; i++) {
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
ret.resize(n,0);
vector<int> ss = {a,b,c};
sort(ALL(Cols),[&](int x, int y){return ss[x-1] < ss[y-1];});
sort(ALL(ss));
A = ss[0], B = ss[1];
bug(A,B,Cols[0],Cols[1]);
dfs(0,-1);
int st = -1;
for (int i = 0; i<n; i++) {
if (sz[i] >= A && n-sz[i] >= B) {
st = i; break;
}
if (sz[i] >= B && n-sz[i] >= A) {
swap(A,B);
swap(Cols[0],Cols[1]);
st = i; break;
}
}
if (st == -1) return ret;
bug(st);
dc(st,pa[st],Cols[0]);
dc(pa[st],st,Cols[1]);
for (int i = 0; i<n; i++) if (ret[i]==0)ret[i] = Cols[2];
return ret;
}
#ifdef BALBIT
signed main(){
IOS();
vector<int> ro = (find_split(6, 3, 1, 2, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5}));
for (int x : ro) cerr<<x<<' ';
}
#endif
