#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+1;
vector<int> g[MAXN];
vector<int> res;
int found;
int n, d[MAXN], subt[MAXN], low[MAXN];
bool vis[MAXN];
int A, B;
void get(int x, int val) {
res[x] = val;
for(int i: g[x]) {
if(d[i] == d[x]+1) {
get(i, val);
}
}
}
void dfs(int x) {
low[x] = d[x], vis[x] = 1, subt[x] = 1;
bool candidate = 1;
int over = 0;
for(int i: g[x]) {
if(!vis[i]) {
d[i] = d[x]+1;
dfs(i);
subt[x] += subt[i], low[x] = min(low[x], low[i]);
if(subt[i] >= A) {
candidate = 0;
}
if(low[i] < d[x]) {
over += subt[i];
}
}
else {
low[x] = min(low[x], d[i]);
}
}
if(!found && candidate && subt[x] >= A) {
if(n-subt[x] + over >= B) {
found = 1;
res.clear(), res.resize(n, 2);
res[x] = 1;
int add = B - (n-subt[x]);
for(int i: g[x]) {
if(add > 0 && d[i] == d[x]+1 && low[i] < d[x]) {
add -= subt[i];
}
else if(d[i] == d[x]+1) {
get(i, 1);
}
}
}
else if(n-subt[x] + over >= A) {
found = 1;
res.clear(), res.resize(n, 1);
res[x] = 2;
int add = A - (n-subt[x]);
for(int i: g[x]) {
if(add > 0 && d[i] == d[x]+1 && low[i] < d[x]) {
add -= subt[i];
}
else if(d[i] == d[x]+1) {
get(i, 2);
}
}
}
}
}
vector<int> tree[MAXN];
int deg[MAXN];
bool vist[MAXN];
void dfst(int x) {
vist[x] = 1;
for(int i: g[x]) {
if(!vist[i] && res[x]==res[i]) {
tree[i].push_back(x), tree[x].push_back(i);
deg[i]++, deg[x]++;
dfst(i);
}
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n = _n;
int m = p.size();
A = min({a, b, c});
B = a+b+c - min({a, b, c}) - max({a, b, c});
for(int i=0; i<m; ++i) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
res.resize(n, 0);
dfs(0);
if(!found) {
return res;
}
vector<pair<int, int>> vec = { make_pair(a, 1), make_pair(b, 2), make_pair(c, 3) };
sort(vec.begin(), vec.end());
int cnt[3] = {0, 0, 0}, rep[3] = {0, 0, 0};
for(int i=0; i<n; ++i) {
assert(res[i] != 0);
cnt[res[i]]++;
rep[res[i]] = i;
}
for(int nr=1; nr<=2; ++nr) {
dfst(rep[nr]);
vector<int> ready;
for(int i=0; i<n; ++i) {
if(res[i]==nr && deg[i]==1) {
ready.push_back(i);
}
}
while(cnt[nr] > vec[nr-1].first) {
assert(ready.size());
int cur = ready.back();
ready.pop_back();
res[cur] = 0;
cnt[nr]--;
for(int i: tree[cur]) {
deg[i]--;
if(deg[i]==1) {
ready.push_back(i);
}
}
}
}
int nrA = vec[0].second, nrB = vec[1].second, nrC = vec[2].second;
for(int i=0; i<n; ++i) {
if(res[i]==1) {
res[i] = nrA;
}
else if(res[i]==2) {
res[i] = nrB;
}
else {
res[i] = nrC;
}
}
return res;
}
