#include "split.h"
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAX_N = 100000;
vector<int> graph[MAX_N];
vector<int> rez;
int target[3];
int color[3];
int subarb[MAX_N];
void colorNodes(int col, int nod, int papa) {
if(target[color[col]] > 0) {
rez[nod] = color[col] + 1;
target[color[col]]--;
} else
rez[nod] = color[2] + 1;
for(auto it: graph[nod])
if(it != papa)
colorNodes(col, it, nod);
}
bool dfs(int N, int nod, int papa = -1) {
subarb[nod] = 1;
for(auto it: graph[nod]) {
if(it != papa) {
bool rez = dfs(N, it, nod);
if(rez == true)
return true;
subarb[nod] += subarb[it];
if(subarb[it] >= target[color[0]] && N - subarb[it] >= target[color[1]]) {
colorNodes(0, it, nod);
colorNodes(1, nod, it);
return true;
} else if(subarb[it] >= target[color[1]] && N - subarb[it] >= target[color[0]]){
colorNodes(1, it, nod);
colorNodes(0, nod, it);
return true;
}
}
}
return false;
}
bool cmp(int a, int b) {
return target[a] < target[b];
}
vector<int> subtask3(int N, int a, int b, int c, vector<int> p, vector<int> q) {
int M = p.size();
rez = vector<int>(N, 0);
for(int i = 0; i < M; ++i) {
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
target[0] = a;
target[1] = b;
target[2] = c;
for(int i = 0; i < 3; ++i)
color[i] = i;
sort(color, color + 3, cmp);
dfs(N, 0);
return rez;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
int M = p.size();
if(M == N) {
p.pop_back();
q.pop_back();
}
if(M == N - 1)
return subtask3(N, a, b, c, p, q);
return rez;
}
