#include "split.h"
#include <assert.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;
}
vi xx;
int pp[N], sz[N], sz_[N], ta[N], tb[N], nxt[N], tail[N], time;
char visited[N]; int qu[N], cnt;
void dfs2(int i) {
int o;
if (i < 0 || xx[i] != -1 || visited[i])
return;
visited[i] = 1, qu[cnt++] = i;
dfs2(pp[i]);
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (ta[j] >= ta[i] && pp[j] != i)
dfs2(j);
}
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (ta[j] >= ta[i] && pp[j] == i)
dfs2(j);
}
}
int k;
void dfs3(int i, int x) {
int o;
if (xx[i] || k == 0)
return;
xx[i] = x, k--;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
dfs3(j, x);
}
}
int a, b, x, y;
int solve(int i) {
int i_, h, h_, sum;
i_ = i;
while (1) {
xx[i_] = -1;
if (i_ == tail[i])
break;
i_ = nxt[i_];
}
cnt = 0;
dfs2(i);
assert(cnt <= 2);
visited[i] = 0;
for (h = 0; h < cnt; h++)
if (sz_[qu[h]] * 2 >= n) {
if (n - sz_[qu[h]] < a) {
for (h = 0; h < cnt; h++)
xx[qu[h]] = 0;
return 0;
}
k = b, xx[qu[h]] = 0, dfs3(qu[h], y);
k = a;
for (h = 0; h < cnt; h++)
if (xx[qu[h]] == -1)
xx[qu[h]] = 0, dfs3(qu[h], x);
return 1;
} else if (sz_[qu[h]] * 3 >= n) {
k = a, xx[qu[h]] = 0, dfs3(qu[h], x);
k = b;
for (h = 0; h < cnt; h++)
if (xx[qu[h]] == -1)
xx[qu[h]] = 0, dfs3(qu[h], y);
return 1;
}
sum = 0;
for (h = 0; h < cnt; h++) {
sum += sz_[qu[h]];
if (sum * 2 >= n) {
k = b;
for (h_ = 0; h_ <= h; h_++)
xx[qu[h_]] = 0, dfs3(qu[h_], y);
k = a;
for (h_ = h + 1; h_ < cnt; h_++)
xx[qu[h_]] = 0, dfs3(qu[h_], x);
break;
} else if (sum * 3 >= n) {
k = a;
for (h_ = 0; h_ <= h; h_++)
xx[qu[h_]] = 0, dfs3(qu[h_], x);
k = b;
for (h_ = h + 1; h_ < cnt; h_++)
xx[qu[h_]] = 0, dfs3(qu[h_], y);
break;
}
}
return 1;
}
int dfs1(int p, int i) {
int o;
pp[i] = p, ta[i] = tb[i] = ++time;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (!ta[j]) {
if (dfs1(i, j))
return 1;
tb[i] = min(tb[i], tb[j]);
if (tb[j] >= ta[i]) {
nxt[i] = j, tail[i] = tail[j], sz_[i] = n - sz[j];
if (solve(i))
return 1;
}
} else if (j != p)
tb[i] = min(tb[i], ta[j]);
}
sz[i] = sz_[i] = 1, tail[i] = i;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
sz[i] += sz[j];
if (ta[j] >= ta[i] && tb[j] < ta[i])
nxt[tail[i]] = j, tail[i] = tail[j];
else
sz_[i] += sz[j];
}
return 0;
}
vi find_split(int n_, int a_, int b_, int c, vi ii, vi jj) {
int m = ii.size(), h, i, 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;
xx.resize(n);
if (dfs1(-1, 0))
for (i = 0; i < n; i++)
if (!xx[i])
xx[i] = x ^ y;
return xx;
}
