#include "split.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n, m;
int aNum;
int bNum;
int cNum;
int timer;
int t[MAXN];
int sz[MAXN];
int low[MAXN];
bool vis[MAXN];
int comp[MAXN];
std::vector <int> g[MAXN];
std::vector <int> tree[MAXN];
std::vector <int> ans;
int a, b, c;
void assignComponent(int node, int to)
{
comp[node] = to;
for (const int &u : tree[node])
{
assignComponent(u, to);
}
}
bool dfs(int node, int par)
{
sz[node] = 1;
vis[node] = true;
t[node] = low[node] = ++timer;
int remove = 0;
std::vector <int> removeAble;
std::vector <int> mandatory;
for (const int &u : g[node])
{
if (u == par)
{
continue;
}
if (vis[u])
{
low[node] = std::min(low[node], t[node]);
continue;
}
tree[node].push_back(u);
if (dfs(u, node))
{
return true;
}
sz[node] += sz[u];
low[node] = std::min(low[node], low[u]);
if (low[u] < t[node])
{
remove += sz[u];
removeAble.push_back(u);
} else
{
mandatory.push_back(u);
}
}
if (sz[node] >= a && remove + n - sz[node] >= b)
{
comp[node] = 1;
for (const int &u : removeAble)
{
if (sz[node] - sz[u] >= a)
{
sz[node] -= sz[u];
} else
{
assignComponent(u, 1);
}
}
for (const int &u : mandatory)
{
assignComponent(u, 1);
}
return true;
}
if (n - sz[node] >= a && sz[node] >= b)
{
std::fill(comp + 1, comp + 1 + n, 1);
comp[node] = 0;
for (const int &u : removeAble)
{
if (sz[node] - sz[u] >= b)
{
sz[node] -= sz[u];
} else
{
assignComponent(u, 0);
}
}
for (const int &u : mandatory)
{
assignComponent(u, 0);
}
return true;
return true;
}
return false;
}
int needed;
void cutComponents(int node)
{
vis[node] = true;
if (needed >= 1)
{
if (comp[node] == 1)
{
ans[node - 1] = aNum;
} else
{
ans[node - 1] = bNum;
}
needed--;
}
for (const int &u : g[node])
{
if (!vis[u] && comp[node] == comp[u])
{
cutComponents(u);
}
}
}
std::vector <int> find_split(int N, int A, int B, int C, std::vector <int> u, std::vector <int> v)
{
n = N;
a = A;
b = B;
c = C;
aNum = 1;
bNum = 2;
cNum = 3;
m = u.size();
if (a > b)
{
std::swap(a, b);
std::swap(aNum, bNum);
}
if (a > c)
{
std::swap(a, c);
std::swap(aNum, cNum);
}
if (b > c)
{
std::swap(b, c);
std::swap(bNum, cNum);
}
for (int i = 0 ; i < m ; ++i)
{
g[u[i] + 1].push_back(v[i] + 1);
g[v[i] + 1].push_back(u[i] + 1);
}
ans.resize(n, 0);
bool res = dfs(1, 0);
if (!res)
{
return ans;
}
std::fill(vis + 1, vis + 1 + n, false);
for (int i = 1 ; i <= n ; ++i)
{
if (vis[i])
{
continue;
}
if (comp[i] == 1) needed = a;
else needed = b;
cutComponents(i);
}
for (int i = 0 ; i < n ; ++i)
{
if (ans[i] == 0)
{
ans[i] = cNum;
}
}
return ans;
}
