#include "bits/stdc++.h"
#include "split.h"
#define MAXN 200005
using namespace std;
int N;
bool vis[MAXN], vis1[MAXN];
int sz[MAXN], color[MAXN];
vector<int> adj[MAXN];
vector<int> nadj[MAXN];
vector<pair<int, int>> v;
bool found = false;
int cnt, q;
void ass1(int node, int num, int par) {
if (cnt >= q)
return;
color[node] = num;
cnt++;
vis1[node] = true;
for (int j : nadj[node]) {
if (j != par && !vis1[j])
ass1(j, num, node);
}
}
void ass2(int node, int num, int par) {
if (cnt >= q)
return;
color[node] = num;
cnt++;
vis1[node] = true;
for (int j : adj[node]) {
if (j != par && !vis1[j])
ass2(j, num, node);
}
}
void dfs(int node, int par) {
if (found)
return;
if (par != -1) {
nadj[par].push_back(node);
nadj[node].push_back(par);
}
sz[node] = 1;
vis[node] = true;
for (int j : adj[node]) {
if (!vis[j]) {
dfs(j, node);
if (found)
return;
sz[node] += sz[j];
}
}
if (found)
return;
if (sz[node] >= v[0].first && N-sz[node] >= v[1].first) {
found = true;
cnt = 0; q = v[0].first;
ass1(node, v[0].second, par);
cnt = 0; q = v[1].first;
ass2(par, v[1].second, node);
} else if (sz[node] >= v[1].first && N-sz[node] >= v[0].first) {
found = true;
cnt = 0; q = v[1].first;
ass1(node, v[1].second, par);
cnt = 0; q = v[0].first;
ass2(par, v[0].second, node);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
v.push_back({a, 1});
v.push_back({b, 2});
v.push_back({c, 3});
sort(v.begin(), v.end());
vector<int> res;
for (int i = 0; i < p.size(); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
/*for (int i = 0; i < n; i++) {
if (!found) {
memset(vis, 0, sizeof vis);
memset(sz, 0, sizeof sz);
dfs(i, -1);
}
}*/
memset(vis, 0, sizeof vis);
memset(sz, 0, sizeof sz);
dfs(0, -1);
if (!found)
return vector<int>(n, 0);
for (int i = 0; i < n; i++) {
if (color[i] == 0)
res.push_back(v[2].second);
else
res.push_back(color[i]);
}
return res;
}
