#include "split.h"
#include <stdlib.h>
using namespace std;
typedef vector<int> vi;
const int N = 100000;
int min(int a, int b) { return a < b ? a : b; }
int *ej[N], eo[N], n;
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int pp[N], sz[N], ta[N], tb[N], i_;
int a, b, x, y, z;
void dfs1(int p, int i) {
static int time;
int o, centroid;
pp[i] = p, ta[i] = tb[i] = ++time;
sz[i] = 1, centroid = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (!ta[j]) {
dfs1(i, j);
if (sz[j] * 2 > n)
centroid = 0;
sz[i] += sz[j];
tb[i] = min(tb[i], tb[j]);
} else if (j != p)
tb[i] = min(tb[i], ta[j]);
}
if ((n - sz[i]) * 2 > n)
centroid = 0;
if (centroid)
i_ = i;
}
vi xx; int k;
void dfs2(int p, int i, int x, int strict) {
int o;
if (xx[i])
return;
xx[i] = k-- > 0 ? x : z;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && (!strict || pp[j] == i || pp[i] == j))
dfs2(i, j, x, strict);
}
}
vi find_split(int n_, int a_, int b_, int c, vi ii, vi jj) {
int m = ii.size(), h, i, j, o, tmp;
n = n_;
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (h = 0; h < m; h++)
append(ii[h], jj[h]), append(jj[h], ii[h]);
a = a_, b = b_;
if (a <= c && b <= c)
x = 1, y = 2;
else if (a <= b && c <= b)
b = c, x = 1, y = 3;
else
a = c, x = 3, y = 2;
if (a > b)
tmp = a, a = b, b = tmp, tmp = x, x = y, y = tmp;
z = x ^ y;
dfs1(-1, 0), i = i_;
if (pp[i] != -1)
sz[pp[i]] = n - sz[i];
xx.resize(n);
for (o = eo[i]; o--; ) {
j = ej[i][o];
if ((j == pp[i] || pp[j] == i) && sz[j] >= a) {
k = a, dfs2(i, j, x, 1);
k = b, dfs2(j, i, y, 1);
return xx;
}
}
k = pp[i] == -1 ? 0 : sz[pp[i]];
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (pp[j] == i && tb[j] < ta[i] && (k += sz[j]) >= a) {
if (k * 2 >= n)
tmp = a, a = b, b = tmp, tmp = x, x = y, y = tmp;
k = b - 1, xx[i] = y;
while (o--) {
j = ej[i][o];
if (pp[j] == i)
dfs2(i, j, y, 1);
}
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (pp[j] == i && tb[j] >= ta[i])
dfs2(i, j, y, 1);
}
k = a, dfs2(i, pp[i], x, 0);
return xx;
}
}
fill_n(xx.begin(), n, 0);
return xx;
}
