#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int n, s[4], t[4], c[100100];
vector<int> r, e[100100];
int dfs(int i) {
r[i] = -1;
c[i] = 1;
for (int j : e[i])
if (!r[j]) {
int k = dfs(j);
c[i] += c[j];
if (c[j] >= s[0]) return k;
}
r[i] = -2;
return i;
}
void dfst(int i, int cr, int k) {
if (!s[k]) return;
r[i] = t[k];
s[k]--;
for (int j : e[i]) if (r[j] == cr) dfst(j, cr, k);
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
n = N;
s[0] = A; s[1] = B; s[2] = C; s[3] = n;
t[0] = 1; t[1] = 2; t[2] = 3; t[3] = -3;
for (int i : {0, 1, 0}) if (s[i] > s[i + 1]) swap(s[i], s[i + 1]), swap(t[i], t[i + 1]);
for (int i = 0; i < (int) p.size(); i++) e[p[i]].push_back(q[i]), e[q[i]].push_back(p[i]);
r.resize(n);
int k = dfs(0);
if (k != 0) {
dfst(k, -2, 3);
r[k] = -4;
for (int i = 0; i < n; i++) r[i] = min(r[i], -2);
if (c[k] >= s[1]) swap(s[0], s[1]), swap(t[0], t[1]);
r[k] = -4;
dfst(0, -2, 1);
for (int i = 0; i < n; i++) if (r[i] == t[1]) for (int j : e[i]) if (r[j] == -3) dfst(j, -3, 1);
r[k] = -3;
dfst(k, -3, 0);
}
if (s[0] || s[1]) r.assign(n, 0);
else for (int i = 0; i < n; i++) r[i] = r[i] < 1 ? t[2] : r[i];
return r;
}
