#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5+5;
int n, m;
vector<int> edges[MAXN];
vector<int> res;
bool vis[MAXN];
int sz[MAXN];
void perm(vector<int> &a, mt19937 &gen) {
for (int i = 1; i < a.size(); i++) swap(a[i], a[gen()%(i+1)]);
}
int dfs(int cur, int a, int b) {
sz[cur] = 1;
vis[cur] = 1;
int ans = -1;
for (int nxt: edges[cur]) {
if (vis[nxt]) continue;
ans = max(dfs(nxt, a, b), ans);
sz[cur] += sz[nxt];
}
if (sz[cur] >= a && n-sz[cur] >= b) ans = 2*cur;
else if (sz[cur] >= b && n-sz[cur] >= a) ans = 2*cur+1;
return ans;
}
void assign(int cur, int spec, bool val, int a[2]) {
vis[cur] = 1;
if (cur == spec) val ^= 1;
if (a[val]) {
res[cur] = val;
a[val]--;
}
for (int nxt: edges[cur]) {
if (vis[nxt]) continue;
assign(nxt, spec, val, a);
}
}
bool test(int a, int b, mt19937 &gen) {
for (int i = 0; i < n; i++) perm(edges[i], gen);
memset(vis, 0, sizeof(bool)*n);
int ans = dfs(0, a, b);
if (ans == -1) return 0;
memset(vis, 0, sizeof(bool)*n);
res = vector<int>(n, 2);
int cur[2]; cur[0] = a; cur[1] = b;
assign(0, ans/2, (ans&1)^1, cur);
return 1;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
m = p.size();
vector<pii> change({{a, 1}, {b, 2}, {c, 3}});
sort(change.begin(), change.end());
a = change[0].first;
b = change[1].first;
for (int i = 0; i < m; i++) {
edges[p[i]].push_back(q[i]);
edges[q[i]].push_back(p[i]);
}
bool f = 0;
mt19937 gen(0);
for (int i = 0; i < 1000; i++) {
if (test(a, b, gen)) {
f = 1;
break;
}
}
if (f) for (int i = 0; i < n; i++) res[i] = change[res[i]].second;
else res = vector<int>(n, 0);
return res;
}
