#include "split.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
inline void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
const int MAXN = 100055;
const int MAXM = 200055;
vector<int> G[MAXN], T[MAXN];
vector<vector<int>> PathV;
int cnt[MAXN], col[MAXN], colcnt[MAXN];
int A[MAXM], B[MAXM];
bitset<MAXN> chk, colchk;
int ud[MAXN];
int Ans[MAXN];
int N, M, CA, CB, CC, CO[4], Rt, K;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
void normdfs(int i, int &c, int key) {
if(!c) return;
chk[i] = false; c--; Ans[i] = key;
for(int v : G[i]) if(chk[v]) normdfs(v, c, key);
}
bool normAns() {
for(int i = 0; i < N; i++) G[i].clear();
for(int i = 0; i < M; i++) fg(G, A[i], B[i]);
chk.reset();
for(int i = 0; i < N; i++)
if(Ans[i] < 1 || 2 < Ans[i]) Ans[i] = 3;
int x = -1;
for(int i = 0; i < N; i++) if(1 == Ans[i]) { x = i; chk[i] = true; }
if(chk.count() < CA) return false;
{ int c = CA; normdfs(x, c, -1); }
for(int i = 0; i < N; i++) {
if(1 == Ans[i]) Ans[i] = 3;
else if(-1 == Ans[i]) Ans[i] = 1;
}
chk.reset();
for(int i = 0; i < N; i++) if(2 == Ans[i]) chk[i] = true;
if(chk.count() < CB) return false;
{ int c = CB; normdfs(Rt, c, -2); }
for(int i = 0; i < N; i++) {
if(2 == Ans[i]) Ans[i] = 3;
else if(-2 == Ans[i]) Ans[i] = 2;
}
return true;
}
void predfs(int i) {
cnt[i] = 1;
for(int v : G[i]) if(!cnt[v]) {
predfs(v);
cnt[i] += cnt[v];
}
}
void cent(int &rt) {
const int N = cnt[rt];
for(int hi, hc;;) {
hi = hc = -1;
for(int v : G[rt]) if(cnt[v] < cnt[rt] && hc < cnt[v]) {
hi = v; hc = cnt[v];
}
if(hc*2 <= N) break;
cnt[rt] = N - hc;
cnt[hi] = N;
rt = hi;
}
}
void treedfs(int i) {
Ans[i] = 1;
for(int v : G[i]) if(cnt[v] < cnt[i])
treedfs(v);
}
bool solveTree() {
for(int v : G[Rt]) if(CA <= cnt[v]) {
fill(Ans, Ans+N, 2);
treedfs(v);
return true;
}
return false;
}
void precoldfs(int i) {
for(int v : G[i]) if(cnt[v] < cnt[i]) {
col[v] = col[i];
precoldfs(v);
}
}
void initNew() {
for(int v : G[Rt]) {
col[v] = K++;
precoldfs(v);
colcnt[col[v]] = cnt[v];
}
for(int i = 0, a, b; i < M; i++) if(A[i] != Rt && B[i] != Rt) {
a = col[A[i]];
b = col[B[i]];
if(a == b) continue;
fg(T, a, b);
}
}
void pathdfs(vector<int> &V, int i) {
colchk[i] = true; V.eb(i);
for(int v : T[i]) if(!colchk[v])
pathdfs(V, v);
}
void getPath() {
for(int i = 0; i < K; i++) if(!colchk[i]) {
PathV.eb();
pathdfs(PathV.back(), i);
}
}
bool solve() {
iota(CO, CO+4, 0);
if(CA > CB) { swap(CA, CB); swap(CO[1], CO[2]); }
if(CA > CC) { swap(CA, CC); swap(CO[1], CO[3]); }
if(CB > CC) { swap(CB, CC); swap(CO[2], CO[3]); }
iota(ud, ud+MAXN, 0);
for(int i = 0, a, b; i < M; i++) {
a = A[i]; b = B[i];
if(uf(a) == uf(b)) continue;
uf(a, b);
fg(G, a, b);
}
predfs(0); cent(Rt);
if(solveTree()) return true;
initNew();
getPath();
for(; !PathV.empty();) {
int sum = 0;
for(int v : PathV.back()) sum += colcnt[v];
if(sum < CA) PathV.pop_back();
else break;
}
if(PathV.empty()) return false;
vector<int> PV;
{
int sum = 0;
for(int v : PathV.back()) {
sum += colcnt[v];
PV.eb(v);
if(sum >= CA) break;
}
}
fill(Ans, Ans+N, 2);
colchk.reset();
for(int v : PV) colchk[v] = true;
for(int i = 0; i < N; i++) if(i != Rt && colchk[col[i]]) Ans[i] = 1;
return true;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
::N = n; ::M = sz(p);
::CA = a; ::CB = b; ::CC = c;
for(int i = 0; i < ::M; i++) {
::A[i] = p[i];
::B[i] = q[i];
}
if(!solve() || !normAns()) return vector<int>(::N, 0);
vector<int> res;
for(int i = 0; i < ::N; i++) {
if(1 == ::Ans[i]) res.eb(::CO[1]);
else if(2 == ::Ans[i]) res.eb(::CO[2]);
else res.eb(::CO[3]);
}
return res;
}
