#include <bits/stdc++.h>
#include "split.h"
using namespace std;
mt19937 rng(15);///everybody wants to...
const int BB = 3e7;
int n, a, b, c, k;
vector<int> g[100005];
vector<int> sol;
int sz[100005];
int dp[100005];
bool fs;
int sub, col, cate, cate2, tat;
bool viz[100005];
int h[100005];
void dfs(int nod, int tt)
{
sz[nod] = 1;
//dp[nod] = n + 1;
viz[nod] = true;
for (auto vecin : g[nod])
{
if (!viz[vecin])
{
h[vecin] = 1 + h[nod];
dfs(vecin, nod);
sz[nod] += sz[vecin];
//dp[nod] = min(dp[nod], dp[vecin]);
}
}
if (!fs and sz[nod] >= a and sz[nod] <= n - a)
{
fs = true;
if (sz[nod] < b)
sub = nod, col = 1, cate = a, cate2 = b, tat = tt;
else
sub = nod, col = 2, cate = b, cate2 = a, tat = tt;
}
}
int ct;
void cd(int nod, int tt, int cl)
{
if (ct == 0)
return;
sol[nod] = cl;
ct--;
viz[nod] = true;
for (auto vecin : g[nod])
{
if (vecin != tt and vecin != sub and h[vecin] == 1 + h[nod])
cd(vecin, nod, cl);
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> U, vector<int> V)
{
n = N;
a = A;
b = B;
c = C;
vector<int> ord(4);
vector<int> ordm1(4);
ord[0] = 0;
ord[1] = 1, ord[2] = 2, ord[3] = 3;
if (a > b)
swap(a, b), swap(ord[1], ord[2]);
if (b > c)
swap(b, c), swap(ord[2], ord[3]);
if (a > b)
swap(a, b), swap(ord[1], ord[2]);
for (int i = 0; i < 4; i++)
ordm1[ord[i]] = i;
for (int i = 0; i < U.size(); i++)
{
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
sol.resize(n);
for (int i = 0; i < n; i++)
sol[i] = 0;
fs = false;
for (int tc = 1; tc <= BB / (n + U.size()); tc++)
{
if (fs)
break;
for (int i = 0; i < n; i++)
shuffle(g[i].begin(), g[i].end(), default_random_engine(rng()));
int r = rng() % n;
for (int i = 0; i < n; i++)
viz[i] = false;
h[r] = 0;
dfs(r, -1);
if (fs)
{
for (int i = 0; i < n; i++)
sol[i] = 3;
ct = cate;
cd(sub, tat, col);
ct = cate2;
cd(r, -1, 3 - col);
}
}
for (int i = 0; i < sol.size(); i++)
sol[i] = ord[sol[i]];
vector<int> fr(4);
for (int i = 0; i < n; i++)
fr[sol[i]]++;
bool all0 = true;
if (fr[1] + fr[2] + fr[3] > 0)
all0 = false;
assert(all0 or (fr[1] == A and fr[2] == B and fr[3] == C));
return sol;
}
