#include "split.h"
using namespace std;
const int maxn = 2e5 + 10;
vector<int> rel[maxn];
int deg[maxn];
vector<int> res(maxn, 3);
vector<bool> used(maxn, 0);
int a, b, c;
int amt = 0;
void dfs (int u) {
if (amt == b) return;
used[u] = 1;
res[u] = 2;
amt++;
for (auto v: rel[u]) {
if (used[v]) continue;
if (amt == b) return;
dfs(v);
}
}
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
a = A;
b = B;
c = C;
for (int i = 0; i < p.size(); i++) {
int u = p[i];
int v = q[i];
rel[u].push_back(v);
rel[v].push_back(u);
deg[u]++;
deg[v]++;
}
int min_deg = maxn;
for (int i = n - 1; i >= 0; i--) {
min_deg = min(min_deg, deg[i]);
}
for (int i = n - 1; i >= 0; i--) {
if (deg[i] == min_deg) {
res[i] = 1;
used[i] = 1;
break;
}
}
if (used[0]) dfs(1);
else dfs(0);
vector<int> ans;
for (int i = 0; i < n; i++) {
ans.push_back(res[i]);
}
return ans;
}
