#include "split.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
vector<pii> edges;
vector<int> A[N];
mt19937_64 rd(time(0));
bool vis[N];
int a, b, c;
int tag[3] = {1, 2, 3};
int n;
void sort_abc()
{
if (a > b) {
swap(a, b);
swap(tag[0], tag[1]);
}
if (b > c) {
swap(b, c);
swap(tag[1], tag[2]);
}
if (a > b) {
swap(a, b);
swap(tag[0], tag[1]);
}
}
int par[N];
int sz[N];
int rt(int v){return par[v]==-1?v:rt(par[v]);}
bool unite(int v, int u)
{
v = rt(v);
u = rt(u);
if (v == u)
return 0;
if (sz[v] < sz[u])
swap(v, u);
sz[v] += sz[u];
par[u] = v;
return sz[v] >= b;
}
void dfs(int v, vector<int> &vec)
{
vis[v] = 1;
vec.push_back(v);
for (int u : A[v])
if (!vis[u])
dfs(u, vec);
}
vector<int> make_ans(vector<int> A, vector<int> B)
{
vector<int> ans(n, tag[2]);
for (int v : A)
ans[v] = tag[0];
for (int v : B)
ans[v] = tag[1];
return ans;
}
pair<vector<int>,vector<int>> test(int v)
{
Loop (i,0,n)
vis[i] = rt(i) != v;
vector<int> A, B;
dfs(v, B);
assert(B.size() >= b);
B.resize(b);
fill(vis, vis+n, 0);
for (int v : B)
vis[v] = 1;
Loop (v,0,n) {
if (vis[v])
continue;
A.clear();
dfs(v, A);
if (A.size() >= a) {
A.resize(a);
return {A, B};
}
}
return {{}, {}};
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n; a = _a; b = _b; c = _c;
sort_abc();
Loop (i,0,p.size()) {
edges.push_back({p[i], q[i]});
A[p[i]].push_back(q[i]);
A[q[i]].push_back(p[i]);
}
Loop (i,0,n)
shuffle(A[i].begin(), A[i].end(), rd);
if (a == 1) {
vector<int> tmp;
dfs(0, tmp);
int v = tmp.back();
tmp.resize(b);
return make_ans({v}, tmp);
}
while (clock() < 1 * CLOCKS_PER_SEC) {
shuffle(edges.begin(), edges.end(), rd);
fill(par, par+n, -1);
fill(sz, sz+n, 1);
for (auto [v, u] : edges) {
if (unite(v, u)) {
auto [A, B] = test(rt(v));
if (A.size())
return make_ans(A, B);
}
}
}
return vector<int>(n, 0);
}
