#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 = 2505;
vector<pii> g[maxn];
vector<int> ret;
vector<int> Cols = {1,2,3};
int sz[maxn];
int pa[maxn];
bool seen[maxn], ok[maxn*4];
int A, B;
void dfs(int v, int p = -1) {
sz[v] = 1;
pa[v] = p;
seen[v] = 1;
for (pii u : g[v]) {
if (u.f!=p && !seen[u.f]) {
ok[u.s] = 1;
dfs(u.f,v);
sz[v] += sz[u.f];
}
}
}
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 (pii u : g[v]) {
if ((c!=Cols[0] || ok[u.s]) && ret[u.f]==0) {
dc(u.f,v,c);
}
}
}
void fs(int n, int a, int b, int c, int start) {
fill(ALL(ret),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];
memset(seen,0,sizeof seen);
memset(ok,0,sizeof ok);
dfs(start,-1);
int st = -1;
for (int i = 0; i<n; i++) {
if (sz[i] >= A && n-sz[i] >= B) {
st = i; break;
}
}
if (st == -1) return;
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];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size();
ret.resize(n,0);
int iter = 0;
for (int i = 0; i<m; i++) {
g[p[i]].pb({q[i],iter++});
g[q[i]].pb({p[i],iter++});
}
for (int i = 0; i<n; i++) {
fs(n,a,b,c,i);
if (ret[0] != 0) {
return ret;
}
}
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
