#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "split.h"
using namespace std;
namespace my {
const int N = 1e5 + 10, INF = 1e9;
mt19937 rnd;
int n;
vector<int> g[N];
void bfs(int v, int d[N]) {
fill_n(d, n, INF);
d[v] = 0;
queue<int> q;
q.push(v);
while (q.size()) {
v = q.front(); q.pop();
for (int u : g[v]) {
if (d[u] > d[v] + 1) {
d[u] = d[v] + 1;
q.push(u);
}
}
}
}
int dv[N], du[N];
pair<vector<int>, vector<int>> solve(int v, int u) {
bfs(v, dv), bfs(u, du);
vector<int> pv, pu;
for (int i = 0; i < n; ++i) {
if (dv[i] < du[i]) {
pv.push_back(i);
} else {
pu.push_back(i);
}
}
sort(all(pv), [&](int i, int j) {
return dv[i] < dv[j];
});
sort(all(pu), [&](int i, int j) {
return du[i] < du[j];
});
return {pv, pu};
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
using namespace my;
n = _n;
vector<int> tmp = {a, b, c};
sort(all(tmp));
a = tmp[0], b = tmp[1], c = tmp[2];
for (int i = 0; i < (int)p.size(); ++i) {
g[p[i]].push_back(q[i]);
}
vector<int> res(n, 0);
for (int it = 0; it < 100; ++it) {
int v = (int)(rnd() % n), u = (int)(rnd() % n);
while (v == u) {
v = (int)(rnd() % n), u = (int)(rnd() % n);
}
tie(p, q) = solve(v, u);
if (p.size() > q.size()) {
swap(p, q);
}
// cout << p.size() << " " << q.size() << endl;
if ((int)p.size() < a || (int)p.size() > a + c) {
continue;
}
assert((int)p.size() >= a && (int)q.size() >= b);
fill(all(res), 3);
for (int i = 0; i < a; ++i) {
res[p[i]] = 1;
}
for (int i = 0; i < b; ++i) {
res[q[i]] = 2;
}
return res;
}
return res;
}
#ifdef LC
#include "grader.cpp"
#endif
