#include "split.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
constexpr ll inf = (1ll<<60);
vector<int> subtask_4(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
ll N = n;
vector<pii> data = {mp(a,1), mp(b,2), mp(c,3)};
sort(all(data));
vii edge(N);
rep(i,0,p.size()){
edge[p[i]].pb(q[i]);
edge[q[i]].pb(p[i]);
}
vector<int> ans(N, data[2].second);
auto modify_all = [&](){
rep(i,0,2){
rep(j,0,N){
if(ans[j] == data[i].second){
vector<bool> visited(N);
ll cnt = 0;
std::function<void(ll)> modify = [&](ll now){
if(cnt < data[i].first){
cnt++;
}
else{
ans[now] = data[2].second;
}
visited[now] = true;
for(auto next: edge[now]){
if(visited[next]) continue;
if(ans[next] != data[i].second) continue;
modify(next);
}
};
modify(j);
break;
}
}
}
return;
};
rep(i,0,N){
vector<bool> used(N);
used[i] = true;
vii v;
for(auto next: edge[i]){
if(used[next]) continue;
vi c;
std::function<void(ll)> dfs = [&](ll now){
c.pb(now);
used[now] = true;
for(auto nex: edge[now]){
if(used[nex]) continue;
dfs(nex);
}
};
dfs(next);
v.pb(c);
}
ll sum = 1;
rep(j,0,v.size()){
sum += v[j].size();
}
rep(j,0,v.size()){
if(v[j].size() < data[0].first) continue;
if(sum-v[j].size() < data[1].first) continue;
rep(k,0,v.size()){
if(j == k) continue;
for(auto el: v[k]) ans[el] = data[1].second;
}
ans[i] = data[1].second;
for(auto el: v[j]) ans[el] = data[0].second;
modify_all();
return ans;
}
rep(j,0,v.size()){
if(v[j].size() < data[1].first) continue;
if(sum-v[j].size() < data[0].first) continue;
rep(k,0,v.size()){
if(j == k) continue;
for(auto el: v[k]) ans[el] = data[0].second;
}
ans[i] = data[0].second;
for(auto el: v[j]) ans[el] = data[1].second;
modify_all();
return ans;
}
}
vector<bool> used(N);
vii v;
rep(i,0,N){
if(used[i]) continue;
vi c;
std::function<void(ll)> dfs = [&](ll now){
c.pb(now);
used[now] = true;
for(auto nex: edge[now]){
if(used[nex]) continue;
dfs(nex);
}
};
dfs(i);
v.pb(c);
}
rep(i,0,v.size()){
rep(j,0,v.size()){
if(i == j) continue;
if(data[0].first > v[i].size()) continue;
if(data[1].first > v[j].size()) continue;
for(auto el: v[i]) ans[el] = data[0].second;
for(auto el: v[j]) ans[el] = data[1].second;
modify_all();
return ans;
}
}
ans.assign(N,0);
return ans;
}
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
if(n <= 2500) return subtask_4(n,a,b,c,p,q);
vector<int> ans(n);
return ans;
}
