#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int A = 1, B = 2, C = 3;
int n, a, b, c, nA, nB, nC;
vector<int> g[maxn], res;
int sz[maxn], h[maxn];
bool visited[maxn];
int dfs3(int v, int col){
visited[v] = 1;
int Tmp = 0;
for (auto u : g[v])
if (!visited[u] and res[v] == res[u])
Tmp += dfs3(u, col-Tmp);
col -= Tmp;
if (col > 0){
nC ++, Tmp++;
if (res[v] == A)
nA --;
else
nB --;
res[v] = C;
}
return Tmp;
}
void dfs2(int v, int col){
res[v] = col;
for (auto u : g[v])
if (h[u] == h[v]+1)
dfs2(u, col);
}
bool dfs(int v){
visited[v] = 1;
sz[v] = 1;
for (auto u : g[v]){
if (!visited[u]){
h[u] = h[v]+1;
if (dfs(u))
return true;
sz[v] += sz[u];
}
}
if (sz[v] >= a and sz[v] <= n-b){
for (int i = 0; i < n; i++)
res[i] = B;
nA = sz[v], nB = n-sz[v];
dfs2(v, A);
return true;
}
if (sz[v] >= b and sz[v] <= n-a){
for (int i = 0; i < n; i++)
res[i] = A;
nB = sz[v], nA = n-sz[v];
dfs2(v,B);
return true;
}
return false;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
if (a > b)
swap(a,b), swap(A,B);
if (c > b)
swap(c,b), swap(B,C);
if (a > b)
swap(a,b), swap(A,B);
::n = n, ::a = a, ::b = b, ::c = c;
for (int i = 0; i < p.size(); i++)
g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
res.resize(n);
if (!dfs(0))
return res;
memset(visited, 0, sizeof visited);
for (int i = 0; i < n; i++){
if (res[i] == A and nA > a)
dfs3(i, nA-a);
if (res[i] == B and nB > b)
dfs3(i, nB-b);
}
return res;
}
