#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"
template<typename T> bool maximize(T &res, const T &val) {if(res > val) return 0; res = val; return 1;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 2e5 + 3;
const int LOG = 20;
const int LIM = 1e6 + 3;
int n, m;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}
vector<int> g[N];
vector<int> tree[N];
int sz[N];
int num[N], low[N];
int vis[N];
int cut[N];
int timedfs = 0;
void dfs(int u, int p)
{
num[u] = low[u] = ++timedfs;
sz[u] = 1;
for(int v : g[u])
{
if(v != p)
if(!num[v])
{
dfs(v, u);
minimize(low[u], low[v]);
tree[u].pb(v);
sz[u] += sz[v];
}
else minimize(low[u], num[v]);
}
}
vector<pii> C;
int get_centroid(int u)
{
for(int v : tree[u]) if(sz[v] >= C[0].fi) return get_centroid(v);
return u;
}
vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q)
{
n = n_;
m = sz(p);
for(int i = 0; i < m; ++i)
{
int u = p[i], v = q[i];
g[u].pb(v);
g[v].pb(u);
}
dfs(0, 0);
C.pb({a, 1});
C.pb({b, 2});
C.pb({c, 3});
sort(all(C));
vector<int> res(n, C[2].se);
function<void(int)> color_1 = [&](int u)
{
if(C[1].fi) res[u] = C[1].se, --C[1].fi;
vis[u] = 1;
for(int v : tree[u]) color_1(v);
};
function<void(int)> color_0 = [&](int u)
{
if(C[0].fi) res[u] = C[0].se, --C[0].fi;
vis[u] = 1;
for(int v : g[u]) if(!vis[v]) color_0(v);
};
int cur = get_centroid(0);
for(int v : tree[cur]) if(low[v] < num[cur] && sz[cur] - sz[v] >= C[0].fi)
{
sz[cur] -= sz[v];
cut[v] = 1;
}
if(n - sz[cur] >= C[1].fi) swap(C[0], C[1]);
if(n - sz[cur] >= C[0].fi)
{
--C[1].fi;
vis[cur] = 1;
res[cur] = C[1].se;
for(int v : tree[cur]) if(!cut[v]) color_1(v);
for(int i = 0; i < n; ++i) if(!vis[i])
{
color_0(i);
break;
}
} else return vector<int>(n, 0);
return res;
}
