#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;
void dfs(int cur, int &b, int col) {
if (b == 0) return;
res[cur] = col;
b--;
for (int nxt: edges[cur]) {
dfs(nxt, b, col);
}
}
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]);
}
int s = 0;
for (int i = 0; i < n; i++) if (edges[i].size() == 1) s = i;
res = vector<int>(n, 2);
dfs(s, b, 1);
for (int i = 0; i < n; i++) {
if (res[i] == 2) {
dfs(i, a, 0);
break;
}
}
assert(a == b && a == 0);
for (int i = 0; i < n; i++) res[i] = change[res[i]].second;
return res;
}
