#include "split.h"
using namespace std;
#define X first
#define Y second
#define pair pair<int, int>
#define pb push_back
#define all(a) a.begin(), a.end()
const int N = 2e5 + 4;
vector<int> adj[N];
vector<vector<int>> V;
bool vis[N];
void dfs(int v) {
vis[v]=1;
V.back().pb(v);
for (int u : adj[v]) if (!vis[u]) dfs(u);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for (int i=0; i<p.size(); i++) {
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
for (int i=0; i<n; i++) if (!vis[i]) {
V.pb({});
dfs(i);
}
vector<pair> ord{{a,1}, {b,2}, {c,3}};
sort(all(ord), [&](auto lhs, auto rhs) {
return lhs.X > rhs.X;
});
sort(all(V), [&](auto &x, auto &y) {
return x.size()<y.size();
});
vector<int> ans(n);
int rep=2;
while (rep--) {
for (auto &vec : V) if (vec.size() >= ord.back().X) {
int t = ord.back().X;
while (t--) {
int v = vec.back();
ans[v] = ord.back().Y;
vec.pop_back();
}
ord.pop_back();
break;
}
}
if (ord.size()>1) return vector(n, 0);
for (int i=0; i<n; i++) if (!ans[i]) ans[i] = ord.back().Y;
return ans;
}
