#include "split.h"
#include <vector>
#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(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>();
}
