#pragma GCC optimize("unroll-loops")
#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> tree[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, int p = -1) {
sz[cur] = 1;
// vis[cur] = 1;
int ans = -1;
for (int nxt: tree[cur]) {
if (nxt == p) continue;
ans = max(dfs(nxt, a, b, cur), 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], int p = -1) {
if (cur == spec) val ^= 1;
if (a[val]) {
res[cur] = val;
a[val]--;
}
for (int nxt: tree[cur]) {
if (nxt == p) continue;
assign(nxt, spec, val, a, cur);
}
}
bool test(int a, int b, mt19937 &gen) {
int s = gen()%n;
for (int i = 0; i < n; i++) {
tree[i].clear();
perm(edges[i], gen);
}
// trial 1: bfs
memset(vis, 0, sizeof(bool)*n);
queue<int> q;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
for (int nxt: edges[t]) {
if (vis[nxt]) continue;
tree[t].push_back(nxt);
vis[nxt] = 1;
q.push(nxt);
}
}
int ans = dfs(s, 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(s, 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 < 100000; i++) {
// perm(edges[i%n], gen);
// perm(edges[(i+n/2)%n], gen);
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;
}
