#include "split.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
int n, m;
int a, b, c;
vvi adj;
vi res;
vb vis;
vi subSize;
ii marked;
vector<ii> types;
int dfs(int node, int parent) {
vis[node] = true;
int maxSize = 0;
for (int child : adj[node]) {
if (vis[child]) continue;
int childSz = dfs(child, node);
maxSize = max(maxSize, childSz);
subSize[node] += childSz;
}
subSize[node]++;
if (maxSize < types[1].first && subSize[node] >= types[1].first && n - subSize[node] >= types[2].first) {
marked = { node, parent };
}
return subSize[node];
}
void partition(int node, int type) {
vis[node] = true;
auto& [nodesLeft, value] = types[type];
if (nodesLeft == 0) {
type = 3;
res[node] = 3;
}
else {
nodesLeft--;
res[node] = value;
}
for (int child : adj[node]) {
if (vis[child]) continue;
if (node == marked.first) {
if (child == marked.second) {
partition(child, 2);
}
else {
partition(child, 1);
}
}
else {
partition(child, type);
}
}
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n, m = (int)p.size();
adj = vvi(n);
a = _a, b = _b, c = _c;
loop(i, m) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vis = vb(n);
subSize = vi(n);
marked = { -1, -1 };
types = {{0, 0}, {a, 1}, {b, 2}, {c, 3}};
sort(all(types));
dfs(0, -1);
res = vi(n);
if (marked == ii{-1, -1}) {
return res;
}
vis = vb(n, false);
partition(marked.first, 1);
return res;
}
