#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
#define x first
#define y second
#define all(v) v.begin(),v.end()
vint solve(int n, int a, int b, vector<vint> &e) {
vector<vint> te(n);
vint pn(n), low(n), mlow(n), sz(n), par(n);
function<void(int, int)> g = [&](int x, int y) {
static int pc = 0;
mlow[x] = pn[x] = ++pc;
sz[x] = 1;
par[x] = y;
low[x] = x;
for(int i : e[x]) {
if(i == y) continue;
if(!pn[i]) {
te[x].push_back(i);
te[i].push_back(x);
g(i, x);
sz[x] += sz[i];
mlow[x] = min(mlow[x], mlow[i]);
}
else {
if(pn[low[x]] > pn[i]) low[x] = i;
}
}
mlow[x] = min(mlow[x], pn[low[x]]);
};
g(0, -1);
function<int(int, int)> f = [&](int x, int y) {
for(int i : te[x]) if(i != y && sz[i] >= a) return f(i, x);
return x;
};
int X = f(0, -1);
for(int &c : te[X]) {
if(mlow[c] < pn[X] && sz[X] - sz[c] >= a) {
sz[X] -= sz[c];
function<int(int, int, int)> rr = [&](int x, int y, int r) {
if(pn[low[x]] < r) {
te[x].push_back(low[x]);
te[low[x]].push_back(x);
return 1;
}
for(int i : te[x]) if(i != y && rr(i, x, r)) return 1;
return 0;
};
rr(c, X, pn[X]);
for(int &y : te[c]) if(y == X) y = -1;
c = -1;
}
}
if(n - sz[X] >= a) {
vint ans(n, 3);
int cnt;
function<void(int, int, int)> h = [&](int x, int y, int c) {
if(cnt) {
cnt--;
ans[x] = c;
}
for(int i : te[x]) if(i >= 0 && i != y) h(i, x, c);
};
int dir = (sz[X] <= n / 2);
cnt = (dir ? a : b);
h(X, par[X], 1 + !dir);
cnt = (dir ? b : a);
h(par[X], X, 1 + dir);
return ans;
}
else return vint(n, 0);
}
vint find_split(int n, int a, int b, int c, vint p, vint q) {
vint v = {0, a, b, c};
vint col = {0, 1, 2, 3};
sort(all(col), [&](int x, int y){ return v[x] < v[y]; });
vector<vint> e(n);
for(int i = 0; i < p.size(); i++) {
e[p[i]].push_back(q[i]);
e[q[i]].push_back(p[i]);
}
vint ans = solve(n, v[col[1]], v[col[2]], e);
for(int &x : ans) x = col[x];
return ans;
}
