#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];
pii elist[2*MAXN];
vector<int> res;
// bool vis[MAXN];
int uf[MAXN];
int rnk[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)]);
}
void perm(pii a[], mt19937 &gen) {
for (int i = 1; i < m; 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);
}
}
int find(int i) {
return uf[i] == -1 ? i : uf[i] = find(uf[i]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (rnk[a] < rnk[b]) swap(a, b);
uf[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
}
bool test(int a, int b, mt19937 &gen, int s) {
for (int i = 0; i < n; i++) {
tree[i].clear();
// perm(edges[i], gen);
}
// trial 2: kruskal
memset(rnk, 0, sizeof(int)*n);
fill(uf, uf+n, -1);
perm(elist, gen);
for (int i = 0; i < m; i++) {
if (find(elist[i].first) != find(elist[i].second)) {
merge(elist[i].first, elist[i].second);
tree[elist[i].first].push_back(elist[i].second);
tree[elist[i].second].push_back(elist[i].first);
}
}
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]);
elist[i] = pii(p[i], q[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, i%n)) {
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;
}
