#include "split.h"
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
vector<int> find_split(int N, int A, int B, int C, vector<int> ea, vector<int> eb) {
int M = ea.size();
vector<vector<int> > G(N);
for(int i = 0; i < M; ++i) {
G[ea[i]].push_back(eb[i]);
G[eb[i]].push_back(ea[i]);
}
bool subtask1 = true;
for(int i = 0; i < N; ++i) {
if(G[i].size() >= 3) {
subtask1 = false;
}
}
if(N <= 1000 && M <= 1000) {
int mn = min({A, B, C});
int mx = max({A, B, C});
int mincol = (A == mn ? 1 : (B == mn ? 2 : 3));
int maxcol = (C == mx ? 3 : (B == mx ? 2 : 1));
int midcol = 6 - mincol - maxcol;
vector<bool> black(N, true); // black = "separate to 3+ components"
vector<int> cutvert(N, -1);
vector<int> sepans(N, -1);
vector<int> weight(N, 0);
for(int i = 0; i < N; ++i) {
vector<int> col(N, -1);
int cnt = 0;
function<void(int, int)> dfs = [&](int pos, int col_) {
col[pos] = col_;
++cnt;
for(int j : G[pos]) {
if(col[j] == -1 && j != i) {
dfs(j, col_);
}
}
};
vector<int> compsize;
for(int j = 0; j < N; ++j) {
if(col[j] == -1 && j != i) {
cnt = 0;
dfs(j, compsize.size());
compsize.push_back(cnt);
}
}
if(compsize.size() >= 3) {
black[i] = true;
int mxptr = max_element(compsize.begin(), compsize.end()) - compsize.begin();
if(compsize[mxptr] < mn) {
return vector<int>(N, 0);
}
else if(mn <= compsize[mxptr] && compsize[mxptr] <= N - mn) {
for(int j = 0; j < N; ++j) {
sepans[j] = (col[j] == mxptr ? 1 : 0);
}
break;
}
else {
for(int j = 0; j < N; ++j) {
if(j != i && col[j] != mxptr) {
cutvert[j] = i;
}
}
weight[i] = N - compsize[mxptr];
}
}
}
if(sepans == vector<int>(N, -1)) {
int initial = -1;
for(int i = 0; i < N; ++i) {
if(cutvert[i] != -1) {
weight[i] = 0;
}
else {
initial = i;
}
}
sepans[initial] = 0;
int sumweight = weight[initial];
while(sumweight < mn) {
for(int j = 0; j < N; ++j) {
if(cutvert[j] != -1 || sepans[j] != -1) {
continue;
}
vector<bool> visncut(N, false);
function<void(int)> dfsncut = [&](int pos) {
visncut[pos] = true;
for(int k : G[pos]) {
if(cutvert[k] == -1 && k != j && sepans[k] == -1 && !visncut[k]) {
dfsncut(k);
}
}
};
int comps = 0;
for(int k = 0; k < N; ++k) {
if(cutvert[k] == -1 && k != j && sepans[k] == -1 && !visncut[k]) {
++comps;
dfsncut(k);
}
}
if(comps == 1) {
sepans[j] = 0;
sumweight += weight[j];
break;
}
}
}
for(int j = 0; j < N; ++j) {
if(cutvert[j] == -1 && sepans[j] == -1) {
sepans[j] = 1;
}
}
for(int j = 0; j < N; ++j) {
if(cutvert[j] != -1) {
sepans[j] = sepans[cutvert[j]];
}
}
}
// suppose "sepans" is determined!
int cntone = 0;
for(int i = 0; i < N; ++i) {
cntone += sepans[i];
}
if(cntone * 2 < N) {
for(int i = 0; i < N; ++i) {
sepans[i] ^= 1;
}
}
int zero = -1, one = -1;
for(int i = 0; i < N; ++i) {
if(sepans[i] == 0 && zero == -1) {
zero = i;
}
if(sepans[i] == 1 && one == -1) {
one = i;
}
}
int rem = 0;
vector<int> ans(N, -1);
function<void(int, int, int)> coloring = [&](int pos, int mode, int col) {
if(rem != 0) {
ans[pos] = col;
--rem;
}
for(int i : G[pos]) {
if(rem > 0 && ans[i] == -1 && sepans[i] == mode) {
coloring(i, mode, col);
}
}
};
rem = mn;
coloring(zero, 0, mincol);
rem = N - mn - mx;
coloring(one, 1, midcol);
for(int i = 0; i < N; ++i) {
if(ans[i] == -1) {
ans[i] = maxcol;
}
}
return ans;
}
else if(subtask1) {
// subtask 1 (7 points)
int ini = 0;
for(int i = 0; i < N; ++i) {
if(G[i].size() == 1) {
ini = i;
break;
}
}
vector<int> seq = { ini };
for(int i = 0; i < N - 1; ++i) {
for(int j : G[seq.back()]) {
if(i == 0 || j != seq[i - 1]) {
seq.push_back(j);
break;
}
}
}
vector<int> ans(N, -1);
for(int i = 0; i < N; ++i) {
if(i < A) ans[seq[i]] = 1;
else if(i < A + B) ans[seq[i]] = 2;
else ans[seq[i]] = 3;
}
return ans;
}
if(A == 1) {
// subtask 2 (11 points)
vector<bool> vis(N, false);
int cnt = 0;
vector<int> ans(N, -1);
function<void(int)> dfs = [&](int pos) {
if(cnt < B) {
++cnt;
ans[pos] = 2;
}
vis[pos] = true;
for(int i : G[pos]) {
if(!vis[i]) {
dfs(i);
}
}
};
dfs(0);
*find(ans.begin(), ans.end(), -1) = 1;
for(int i = 0; i < N; ++i) {
if(ans[i] == -1) ans[i] = 3;
}
return ans;
}
if(M == N - 1) {
// subtask 3 (22 points)
vector<int> par(N), subtree(N, 1);
function<void(int, int)> build_tree = [&](int pos, int pre) {
par[pos] = pre;
for(int i : G[pos]) {
if(i != pre) {
build_tree(i, pos);
subtree[pos] += subtree[i];
}
}
};
build_tree(0, -1);
int mn = min({A, B, C});
int mx = max({A, B, C});
int spl = -1;
for(int i = 0; i < N; ++i) {
if(mn <= subtree[i] && subtree[i] <= N - mn) {
spl = i;
break;
}
}
if(spl == -1) {
return vector<int>(N, 0);
}
int mincol = (A == mn ? 1 : (B == mn ? 2 : 3));
int maxcol = (C == mx ? 3 : (B == mx ? 2 : 1));
int midcol = 6 - mincol - maxcol;
vector<int> ans(N, -1);
int rem = 0;
function<void(int, int, int)> coloring = [&](int pos, int pre, int col) {
if(rem > 0) {
ans[pos] = col;
--rem;
}
for(int i : G[pos]) {
if(i != pre) {
coloring(i, pos, col);
}
}
};
rem = mn;
if(subtree[spl] * 2 <= N) {
coloring(spl, par[spl], mincol);
}
else {
coloring(par[spl], spl, mincol);
}
rem = N - mn - mx;
if(subtree[spl] * 2 <= N) {
coloring(par[spl], spl, midcol);
}
else {
coloring(spl, par[spl], midcol);
}
for(int i = 0; i < N; ++i) {
if(ans[i] == -1) {
ans[i] = maxcol;
}
}
return ans;
}
return vector<int>();
}
