#include <bits/stdc++.h>
#include "split.h"
using namespace std;
mt19937 rng(15);///everybody wants to...
const int BB = 5e7;
int n, a, b, c;
vector<int> g[100005];
vector<int> f[100005];
vector<int> be[100005], fe[100005];
bool viz[100005];
int t[100005];
int sz[100005];
int h[100005];
vector<int> sol;
void dfs(int nod)
{
viz[nod] = true;
sz[nod] = 1;
for (auto fiu : g[nod])
{
if (!viz[fiu])
{
t[fiu] = nod;
h[fiu] = 1 + h[nod];
f[nod].push_back(fiu);
dfs(fiu);
sz[nod] += sz[fiu];
}
else if (fiu != t[nod])
{
be[nod].push_back(fiu);
fe[fiu].push_back(nod);
}
}
}
vector<int> subarb;
void gs(int nod)
{
subarb.push_back(nod);
for (auto fiu : f[nod])
gs(fiu);
}
void get_subarb(int nod)
{
subarb.clear();
gs(nod);
}
int ct;
void bro(int nod, int cl, int blk)
{
if (ct == 0)
return;
sol[nod] = cl;
ct--;
for (auto fiu : f[nod])
if (fiu != blk)
bro(fiu, cl, blk);
}
void fin(int r, int fiu)
{
//cout << r << ' ' << fiu << endl;
for (int i = 0; i < n; i++)
sol[i] = 3;
if (sz[fiu] < b)
{
int cl;
cl = 1, ct = a;
bro(fiu, cl, -1);
cl = 2, ct = b;
bro(0, cl, fiu);
}
else
{
int cl;
cl = 2, ct = b;
bro(fiu, cl, -1);
cl = 1, ct = a;
bro(0, cl, fiu);
}
}
void fin2(int r, vector<int> cine, vector<int> cine2)
{
/*for (auto it : cine)
cout << it << ' ';
cout << endl;
for (auto it : cine2)
cout << it << ' ';
cout << endl;*/
int suma = n - sz[r];
for (auto it : cine)
suma += sz[it];
for (int i = 0; i < n; i++)
sol[i] = 3;
if (suma < b)
{
int cl;
cl = 1, ct = a;
bro(0, cl, r);
for (auto fiu : cine)
bro(fiu, cl, -1);
cl = 2, ct = b;
sol[r] = 2;
ct--;
for (auto fiu : cine2)
bro(fiu, cl, -1);
}
else
{
int cl;
cl = 2, ct = b;
bro(0, cl, r);
for (auto fiu : cine)
bro(fiu, cl, -1);
cl = 1, ct = a;
sol[r] = 1;
ct--;
for (auto fiu : cine2)
bro(fiu, cl, -1);
}
}
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;
dfs(0);
int r = 0;
while (true)
{
int fu = -1;
for (auto fiu : f[r])
if (sz[fu] > n - a)
r = fu;
if (fu == -1)
break;
}
int coef = n - sz[r];
bool gata = false;
for (auto fiu : f[r])
{
if (sz[fiu] >= a)
{
fin(r, fiu);
gata = true;
break;
}
}
if (!gata)
{
vector<int> cine, cine2;
for (auto fiu : f[r])
{
//cout << "ya" << endl;
bool con = false;
get_subarb(fiu);
for (auto it : subarb)
for (auto itt : be[it])
if (h[itt] < h[r])
con = true;
if (con and coef < a)
{
cine.push_back(fiu);
coef += sz[fiu];
}
else
cine2.push_back(fiu);
}
if (coef >= a)
fin2(r, cine, cine2);
else
{
for (int i = 0; i < n; i++)
sol[i] = 0;
}
}
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;
}
